Recursive Functions

📖
Recursion

When a function calls itself to solve smaller versions of the same problem.

Classic example: Factorial (5! = 5 × 4 × 3 × 2 × 1)

def factorial(n):
    # Base case: stop condition
    if n == 0 or n == 1:
        return 1
    
    # Recursive case: call itself   
    return n * factorial(n - 1)

print(factorial(5))  # 120

How it works:

factorial(5) = 5 × factorial(4)
             = 5 × (4 × factorial(3))
             = 5 × (4 × (3 × factorial(2)))
             = 5 × (4 × (3 × (2 × factorial(1))))
             = 5 × (4 × (3 × (2 × 1)))
             = 120

Key parts of recursion:

📝
Recursion Checklist

1. Base case: When to stop
2. Recursive case: Call itself with simpler input
3. Progress: Each call must get closer to the base case

Another example: Countdown

def countdown(n):
    if n == 0:
        print("Blast off!")
        return
    print(n)
    countdown(n - 1)

countdown(3)
# Output: 3, 2, 1, Blast off!
⚠️
Watch Out

Deep recursion can cause memory issues. Python has a default recursion limit.