8.6. Recursion in Python

A function calling itself.

Recursion occurs when a function calls itself to solve a problem. This approach is often used to break down complex problems into simpler sub-problems that are easier to manage. When designing a recursive function, it's essential to identify a base case, which is a stopping condition that prevents infinite loops, and a recursive case, where the function continues to call itself with new parameters.

Imagine a set of nesting dolls (Matryoshka dolls). When you open one doll, you find another smaller doll inside, and this process continues until you reach the smallest doll. Recursion works in a similar way: each call to the function can open up a 'new doll' (a new problem) until it reaches a solvable scenario (the smallest doll).

Example: Factorial using Recursion

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)
print(factorial(5)) # Output: 120

The provided code snippet demonstrates a recursive function that calculates the factorial of a number. The function 'factorial' takes a single argument 'n'. The base case is if n == 1: return 1, which means that if the input is 1, the function should return 1. If it's greater, it returns 'n' multiplied by the factorial of 'n-1'. So, for example, factorial(5) results in 5 * factorial(4). This process continues until it reaches the base case.

Think of factorial as a series of steps in a staircase. To get to the top (factorial of 5), you first take one step to the fifth stair (5), then to the fourth stair (4), and so on, until you reach the first stair (1), where you pause. When you add up all the steps you took, it is similar to how the factorial calculation accumulates the values through each recursive call.

Be cautious: Recursion can lead to memory overflow if not handled correctly.

While recursion can be a powerful tool, it must be used carefully. Each recursive call takes up a portion of memory on the call stack. If a function calls itself too many times without hitting the base case, it can exhaust the available memory, leading to a 'stack overflow' error. Therefore, always ensure your recursive functions have a well-defined base case, and consider the maximum depth to avoid hitting memory limits.

Consider a library shelving system where books are stored in a strict order. If you keep taking out books to find a misplaced one but forget to stop (i.e., you have no limit on how long you search), soon you'll have so many books in your arms that you can't hold them all anymore. Similar to this, without a boundary in recursion, you risk overflowing the available 'holding space' (memory).

--