Recursion in Python

Recursion is when a function calls itself to solve a smaller piece of the same problem. The classic example is the factorial of a number:

def factorial(n):
    # Base case: stop when n reaches 1
    if n <= 1:
        return 1
    # Recursive case: n times the factorial of (n-1)
    return n * factorial(n - 1)

print(factorial(5))    # 120  (5 * 4 * 3 * 2 * 1)

Every recursive function needs two things: a base case that stops the recursion, and a recursive case that moves toward that base case. Let's see why.

How recursion works

When factorial(5) runs, it can't finish until it knows factorial(4), which needs factorial(3), and so on down to factorial(1). That last call returns 1 without calling itself — the base case. Then the answers multiply back up:

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

The base case is the most important part. Without it, the function would call itself forever.

The base case: the safety brake

A recursive function with no base case (or one it never reaches) keeps calling itself until Python gives up with a RecursionError: maximum recursion depth exceeded. Always ask: "What is the simplest input where I already know the answer?" That's your base case.

def countdown(n):
    if n == 0:           # base case
        print("Liftoff!")
        return
    print(n)
    countdown(n - 1)     # each call gets closer to 0

countdown(3)
# 3
# 2
# 1
# Liftoff!

Another classic: Fibonacci

The Fibonacci sequence (0, 1, 1, 2, 3, 5, 8, ...) is defined recursively — each number is the sum of the two before it:

def fibonacci(n):
    # Two base cases for the first two numbers
    if n == 0:
        return 0
    if n == 1:
        return 1
    # Recursive case
    return fibonacci(n - 1) + fibonacci(n - 2)

Print the first 8 Fibonacci numbers

for i in range(8): print(fibonacci(i), end=" ")

0 1 1 2 3 5 8 13

This works, but it's slow for large `n` because it recomputes the same values many times. That's a known limitation of naive recursion.

## Recursion vs loops

Anything you can do with recursion you can usually also do with a loop, and vice versa. Recursion is elegant for problems that are naturally "nested" — like exploring folders inside folders, or tree structures. For simple repetition, a loop is often clearer and faster:

```python
# Factorial using a loop instead of recursion
def factorial_loop(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print(factorial_loop(5))   # 120

Common mistakes

• No base case: The function calls itself forever and crashes with RecursionError. Always include a stopping condition.
• Base case never reached: If the recursive call doesn't move toward the base case (e.g. you call factorial(n) instead of factorial(n - 1)), it still recurses infinitely.
• Forgetting to return the recursive call: Writing factorial(n - 1) without return loses the result. The recursive call's value must be returned or used.
• Using recursion for huge inputs: Python limits recursion depth (around 1000 by default). For deep problems, a loop or an iterative approach is safer.
• Expecting recursion to be fast: Naive recursion (like Fibonacci) can be slow due to repeated work. Techniques like memoization fix this, but learn the basics first.

FAQ

What is the maximum recursion depth in Python? By default it's about 1000 calls. You can check it with sys.getrecursionlimit(). Going past it raises RecursionError.

Is recursion better than loops? Neither is universally better. Recursion is cleaner for nested or tree-like data; loops are simpler and faster for straightforward repetition.

Can I speed up recursive functions? Yes — using functools.lru_cache to cache results (memoization) dramatically speeds up things like Fibonacci. That's an intermediate topic worth exploring later.

---

Recursion builds directly on Functions in Python, so make sure you're comfortable there first. You may also enjoy seeing recursion applied to Lambda Functions in Python. More on the Python learning hub.

Want to learn this properly? Join the waitlist for our Python course — taught in Jalgaon, beginner-friendly.