Understanding Recursion in Python: So, are you going to face it?

Recursion is a fundamental concept in programming, but sometimes it can seem a bit mysterious. So, let's simplify this and see that it's easier than it seems!

What is Recursion?

Recursion is when a function solves a problem by calling... itself! Yes, that's right. It works like a story that you tell over and over again, only a little shorter each time until you reach the end. But for it to work properly, it needs to meet two golden rules:

1. Termination Condition: it is the point where the function must stop, otherwise it will stay in an eternal loop (we don't want that, right?).
2. Self-call: this is when the function calls itself, going deeper and deeper until it reaches the termination condition.

Now, let's see how this works in practice!

How does it work?

To explain it better, nothing better than the classic example of factorial! Imagine we want to calculate (5!) (read "five factorial"). How does it work?

5! = 5 * 4 * 3 * 2 * 1!

However, with recursion, we can think of it like this:

5! = 5 * 4!

And, in sequence, 4! is (4 * 3!), and so on, until we reach (1!), which is our base case (the termination condition).

Practical Example: Factorial

Let's get to the code, because that's where the concept comes to life! Here is the famous factorial calculation using recursion:

def fatorial(numero):
    if numero == 0 or numero == 1:
        return 1  # caso base
    else:
        return numero * fatorial(numero - 1)

Explanation:

1. The base case here is when the number is 0 or 1, where the function simply returns 1.
2. If the number is greater than 1, the function is called with number - 1, accumulating the values ​​up to the base case.

Complexity

• Time: (O(n)) — since there are n recursive calls.
• Space: (O(n)) — execution stack depth is n.

Practical Example: Fibonacci

Another widely used example is the Fibonacci sequence. She's like this:

f(0) = 0, f(1) = 1, f(n) = f(n - 1) f(n - 2)

Let's get to the code!

def seq_fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n > 1:
        return seq_fib(n - 1) + seq_fib(n - 2)

Fibonacci Complexity:

• Time: (O(2^n)) — exponential! ⚠️
• Space: (O(n)) — stack usage for recursive calls.

That's why, for large values, the Fibonacci calculation with pure recursion can be a bit cumbersome. But for learning purposes, it's a great example!

Finally

Recursion is a key concept in programming and, although it may seem a little intimidating at first, it becomes much easier with practice. These factorial and Fibonacci examples are just the beginning!

If you want to practice, check it out and make a copy, in this Colab here!

The above is the detailed content of Understanding Recursion in Python: So, are you going to face it?. For more information, please follow other related articles on the PHP Chinese website!