In Python, Recursion is a programming technique where a function calls itself directly or indirectly to solve a problem. It is based on the "divide and conquer" strategy—breaking a complex problem down into smaller, similar sub-problems until they are simple enough to be solved directly.

1. Theoretical Overview

The Two Essential Components

For a recursive function to work correctly and avoid running forever, it must have two parts:

1. The Base Case: The condition under which the function stops calling itself. Without a base case, the function would result in an infinite loop (and eventually a RecursionError).

2. The Recursive Step: The part of the function where it calls itself with a modified (usually smaller) argument, moving closer to the base case.

How it Works (The Call Stack)

When a function calls itself, the current execution is paused, and a new "frame" is added to the Call Stack. Each frame stores the local variables and the point where the code should resume. Once the base case is reached, the stack starts "unwinding," returning values back up the chain until the original call is resolved.

2. Code Implementation: The Factorial Example

The classic example of recursion is calculating the factorial of a number ($n!$).

• $5! = 5 \times 4 \times 3 \times 2 \times 1$

• Recursive Logic: $n! = n \times (n-1)!$

def factorial(n):
    """Calculates factorial using recursion."""
    # 1. Base Case: If n is 0 or 1, return 1
    if n <= 1:
        return 1
    
    # 2. Recursive Step: n * factorial of (n-1)
    else:
        return n * factorial(n - 1)

# Example Usage
num = 5
print(f"The factorial of {num} is {factorial(num)}") 
# Output: 120

3. Visualizing the Process ($n=3$)

1. factorial(3) calls 3 * factorial(2)

2. factorial(2) calls 2 * factorial(1)

3. factorial(1) reaches the Base Case, returns 1

4. Unwinding: 2 * 1 returns 2

5. Final result: 3 * 2 returns 6

4. Advantages and Disadvantages

5. Important Python Limit

Python has a default limit on how deep recursion can go (usually 1,000 calls) to protect your computer from crashing due to an infinite loop.

import sys
# Check the limit
print(sys.getrecursionlimit())