Recursion

Definition: Recursion is a programming technique where a function calls itself directly or indirectly to solve a problem by breaking it down into smaller, manageable sub-problems.

Why: Recursion is a powerful alternative to loops for problems that have a naturally repetitive or nested structure (such as calculating factorials, generating Fibonacci numbers, or traversing folder trees).

The Two Core Components of Recursion

• Base Case: The condition that stops the recursion. Without a base case, the function would call itself indefinitely and crash the program.
• Recursive Case: The part of the function where it calls itself, usually with a slightly modified or smaller input, moving closer to the base case.

Example (Calculating Factorial)

def factorial(n):
    # Base Case: 0! is 1
    if n == 0:
        return 1
    
    # Recursive Case: n! = n * (n-1)!
    return n * factorial(n - 1)

print(factorial(5))  # Output: 120

Explanation

When you call factorial(5), Python opens multiple layers of function execution like a stack of blocks:

• factorial(5) returns 5 * factorial(4)
• factorial(4) returns 4 * factorial(3)
• factorial(3) returns 3 * factorial(2)
• factorial(2) returns 2 * factorial(1)
• factorial(1) returns 1 * factorial(0)
• factorial(0) hits the base case and returns 1.

Once the base case is reached, Python works backward, multiplying the values together to return the final answer of 120.

Key Notes

• Stack Overflow: If you forget a base case or your logic doesn't reach it, Python will trigger a RecursionError (maximum recursion depth exceeded).
• Performance: While elegant, recursive functions can use more memory than regular loops because each self-call adds a new layer to the system's call stack.