Recursion in Python

Recursion is a technique where a function calls itself to solve a problem by breaking it into smaller pieces. It’s a fundamental concept in computer science that appears in algorithms, data structures, and many real-world problems.

What Is Recursion?

A recursive function calls itself. Each call solves a smaller piece of the problem until it reaches a simple case that doesn’t need further recursion.

Every recursive function needs two parts:

• Base case: The condition where the function stops calling itself
• Recursive case: The part where the function calls itself with modified arguments

Think of it like counting down from a number. You keep subtracting until you hit zero, then you stop.

Your First Recursive Function

Let’s start with a simple countdown:

def countdown(n):
    if n <= 0:
        return
    print(n)
    countdown(n - 1)

countdown(5)

The function prints the number, then calls itself with n - 1. When n becomes 0 or less, it hits the base case and returns.

The Classic Example: Factorial

The factorial of a number n (written n!) is the product of all positive integers from 1 to n. For example, 5! = 5 × 4 × 3 × 2 × 1 = 120.

Here’s how you’d calculate it recursively:

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))  # Output: 120

Walk through what happens when you call factorial(5):

1. factorial(5) calls factorial(4) and returns 5 * 24
2. factorial(4) calls factorial(3) and returns 4 * 6
3. factorial(3) calls factorial(2) and returns 3 * 2
4. factorial(2) calls factorial(1) and returns 2 * 1
5. factorial(1) hits the base case and returns 1

The calls unwind: 2 * 1 = 2, then 3 * 2 = 6, then 4 * 6 = 24, then 5 * 24 = 120.

Sum a List Recursively

Another common pattern is processing a list by handling the first element and recursing on the rest:

def sum_list(lst):
    if not lst:
        return 0
    return lst[0] + sum_list(lst[1:])

print(sum_list([1, 2, 3, 4, 5]))  # Output: 15

This works because each recursive call processes one element at a time. The list gets smaller with each call until it becomes empty, triggering the base case.

Fibonacci Sequence

The Fibonacci sequence starts with 0 and 1, each subsequent number is the sum of the two preceding ones:

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

for i in range(10):
    print(fibonacci(i), end=' ')  # Output: 0 1 1 2 3 5 8 13 21 34

This is a classic example, but it’s slow for large n because it recalculates the same values many times.

The Recursion Limit

Python raises a RecursionError when the call stack gets too deep. You can check the limit:

import sys
print(sys.getrecursionlimit())  # Output: 1000

You can increase this limit, but be careful:

sys.setrecursionlimit(2000)

In practice, hitting the recursion limit usually means your base case is wrong or missing.

Understanding the Call Stack

When a function calls itself, Python creates a new frame on the call stack. Each recursive call gets its own frame with its own local variables. This is why recursive functions can track progress through multiple levels of calls.

When the base case is reached, the stack begins to unwind. Each level returns its result to the level below it, combining results as the calls return in reverse order.

For example, with factorial(4):

• First, frames are pushed: factorial(4), factorial(3), factorial(2), factorial(1)
• factorial(1) returns 1
• Then frames pop: factorial(2) returns 21=2, factorial(3) returns 32=6, factorial(4) returns 4*6=24

This stack-based behavior is why recursion uses memory proportional to the depth of the recursion.

When to Use Recursion

Recursion works well for problems with a recursive structure:

• Tree traversal and hierarchical data
• Graph algorithms like depth-first search
• Divide and conquer algorithms like merge sort
• Mathematical sequences like factorial and Fibonacci
• Processing nested structures like JSON

Recursion vs Iteration

You can solve most recursive problems with loops too:

# Iterative factorial
def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

The iterative version is often clearer for simple problems. Recursion shines when the problem has a naturally recursive structure.

Tail Recursion

Tail recursion occurs when the recursive call is the last thing the function does. Some languages optimize this to reuse the same stack frame. Python does not optimize tail recursion, but you can sometimes rewrite recursive functions to be iterative.

Common Pitfalls

The most common mistake is forgetting the base case, which causes infinite recursion. Another pitfall is stack overflow with large inputs. Python’s default limit of 1000 calls is usually enough for most problems.

A well-designed recursive function should:

• Have a clear base case that always terminates
• Make progress toward the base case with each call
• Not rely on shared mutable state between calls

Practice Problems

Here are some problems to practice recursion:

1. Reverse a string: Return the characters in reverse order
2. Check palindrome: Determine if a string reads the same forwards and backwards
3. Find maximum: Locate the largest value in a list

Try tracing through these by hand to understand how each recursive call works.

Next Steps

Recursion is a powerful tool that shows up in many algorithms. Try implementing these recursively:

• Reversing a string
• Finding the maximum value in a list
• Checking if a string is a palindrome

Continue with the next tutorial in the series to learn about other ways to structure your code.