The Call Stack, Fibonacci, Advantages and Pitfalls

The Call Stack, Fibonacci, Advantages and Pitfalls

When a recursive function runs, each call is stacked in memory in what is called the call stack: Python keeps in memory the state of each pending call (its local variables, the point where the computation should resume), until the deepest call (the base case) returns its value. The results then move back up the stack, one call after another, up to the very first call.

A more complex example: the Fibonacci sequence, where each term is the sum of the two preceding ones (0, 1, 1, 2, 3, 5, 8...):

def fibonacci(n):
    if n <= 1:
        return n                                  # (base case)
    else:
        return fibonacci(n - 1) + fibonacci(n - 2) # (recursive case, two calls)

print(fibonacci(5))   # (prints 5)

Here, each call triggers two new ones, which makes the total number of calls grow very quickly: this is one of the pitfalls of recursion.

Advantages of recursion:

• code that is often shorter and closer to the problem's mathematical definition,
• particularly well suited to structures that are naturally defined recursively (trees, nested folders...).

Pitfalls to be aware of:

• infinite recursion: a missing or never-reached base case triggers a RecursionError,
• the cost in memory and time: each call takes up space on the stack, and some functions (like fibonacci above) recompute the same values several times, which can become very slow for large numbers.

In short, recursion is a powerful tool, to be used when it truly makes the code clearer, but never without having checked that a base case exists and will actually be reached.