Python Recursion

Recursion is when a function calls itself in order to solve a smaller version of the same problem, until it reaches a case simple enough to answer directly. It’s one of the most powerful ideas in programming because many real-world problems — walking a file system, parsing nested data, searching a tree, computing mathematical sequences — are naturally defined in terms of themselves. Once you understand how Python manages the calls under the hood, recursion stops feeling like magic and becomes just another tool for breaking problems into smaller pieces.

Overview: How Recursion Works

Every recursive function has two essential parts:

• Base case — the condition where the function returns a value directly, without calling itself again. This is what stops the recursion.
• Recursive case — the part where the function calls itself with an argument that is closer to the base case (usually smaller, shorter, or simpler).

Internally, every function call in Python — recursive or not — creates a new stack frame on the call stack. A stack frame stores that call’s local variables, its arguments, and the point in the code it should return to once it finishes. When factorial(5) calls factorial(4), Python doesn’t reuse the existing frame; it pushes a brand-new frame on top of the stack, completely separate from the one that called it. Each frame has its own copy of n, so the calls don’t interfere with each other. The function keeps calling itself and pushing new frames until it hits the base case, at which point the stack starts “unwinding” — each frame returns its value to the frame that called it, and Python pops frames off the stack one by one until control returns to the original caller.

This matters for two practical reasons. First, the call stack has a limit — CPython defaults to about 1000 nested calls (check it with sys.getrecursionlimit()). Exceed it and Python raises a RecursionError rather than crashing the interpreter or corrupting memory. Second, unlike some languages, CPython does not perform tail-call optimization. Even if your recursive call is the very last thing your function does, Python still keeps every frame on the stack until the whole chain unwinds. That means deep recursion in Python is genuinely more memory-hungry than an equivalent loop, which is one reason iteration is often preferred for simple counting or accumulation tasks, while recursion shines for data that is recursively shaped, such as trees, nested lists, or JSON-like structures.

Syntax

There’s no special keyword for recursion in Python — any function is recursive if it calls itself by name somewhere in its own body:

def function_name(parameters):
    if base_case_condition:
        return base_case_value
    return function_name(smaller_or_simpler_arguments)

Part	Purpose
base_case_condition	A check that stops the recursion once the problem is trivial to solve.
base_case_value	The direct answer returned with no further recursive calls.
function_name(...)	The recursive call — must move the argument(s) toward the base case, or the function never stops.

Examples

Example 1: Factorial

def factorial(n):
    if n < 0:
        raise ValueError("n must be non-negative")
    if n == 0:
        return 1
    return n * factorial(n - 1)

print(factorial(5))
print(factorial(0))
print(factorial(10))

Output:

120
1
3628800

The base case is n == 0, which returns 1 directly. Every other call multiplies n by the result of factorial(n - 1), so factorial(5) becomes 5 * 4 * 3 * 2 * 1 * 1 once every frame unwinds.

Example 2: Summing a List Recursively

def recursive_sum(numbers):
    if not numbers:
        return 0
    return numbers[0] + recursive_sum(numbers[1:])

data = [4, 8, 15, 16, 23, 42]
print(recursive_sum(data))
print(recursive_sum([]))

Output:

108
0

Here the base case is an empty list, which sums to 0. Each recursive call slices off the first element and passes the rest of the list along, so the list gets one element shorter on every call until it’s empty. Slicing creates a new list each time, which is simple to reason about but costs extra memory for very large lists — a plain loop or sum() would be more efficient in production code.

Example 3: Fibonacci with Memoization

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n: int) -> int:
    if n < 2:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

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

print(fibonacci(30))

Output:

0 1 1 2 3 5 8 13 21 34 
832040

A naive recursive Fibonacci function recalculates the same values over and over — fibonacci(5) calls fibonacci(3) twice, fibonacci(2) three times, and so on, growing exponentially. The @lru_cache decorator from functools caches each result the first time it’s computed, so repeated calls with the same argument return instantly instead of recomputing. This turns an exponential-time function into a linear-time one, and it’s why fibonacci(30) returns immediately instead of taking noticeably long.

Under the Hood: Tracing the Call Stack

Walking through factorial(4) step by step makes the stack behavior concrete:

1. factorial(4) is called. n != 0, so it needs the result of factorial(3) before it can return. Its frame stays on the stack, waiting.
2. factorial(3) is called, pushing a new frame. It needs factorial(2).
3. factorial(2) is called, needs factorial(1).
4. factorial(1) is called, needs factorial(0).
5. factorial(0) is called. This hits the base case and returns 1 immediately — no further calls.
6. Now the stack unwinds: factorial(1) receives 1, computes 1 * 1 = 1, and returns.
7. factorial(2) receives 1, computes 2 * 1 = 2, and returns.
8. factorial(3) receives 2, computes 3 * 2 = 6, and returns.
9. factorial(4) receives 6, computes 4 * 6 = 24, and returns 24 to the original caller.

At the deepest point, five frames (factorial(4) through factorial(0)) exist simultaneously in memory, each with its own n. That’s the concrete cost of recursion: time proportional to the depth of the calls, and memory proportional to how many frames are alive at once.

Common Mistakes

Mistake 1: Forgetting the base case

If a recursive function has no condition that stops it, it will call itself forever — or more precisely, until Python’s call stack limit is reached and it raises a RecursionError:

def factorial_broken(n):
    return n * factorial_broken(n - 1)  # no base case, never stops!

print(factorial_broken(5))

Calling factorial_broken(5) triggers factorial_broken(4), then factorial_broken(3), then factorial_broken(2), factorial_broken(1), factorial_broken(0), factorial_broken(-1), and so on with no way to stop, eventually raising RecursionError: maximum recursion depth exceeded. Every recursive function needs at least one condition that returns a value without recursing.

Mistake 2: Forgetting to use the recursive call’s return value

def factorial_no_return(n):
    if n == 0:
        return 1
    factorial_no_return(n - 1)  # result is discarded!

print(factorial_no_return(5))

Output:

None

The recursive call does happen, and the recursion does terminate correctly, but the result of factorial_no_return(n - 1) is never combined with n or returned — the function falls off the end and implicitly returns None. Whenever a recursive case needs the result of the smaller subproblem, that result must be captured with return (or otherwise used), not just called for its side effects.

Best Practices

• Always write the base case first and make sure it’s reachable — trace through what happens on the smallest possible input before worrying about the general case.
• Make sure every recursive call moves the argument strictly closer to the base case (smaller number, shorter sequence, fewer nested elements).
• Prefer a simple for or while loop for straightforward counting or accumulation — Python has no tail-call optimization, so deep recursion uses more memory than an equivalent loop.
• Reach for recursion when the data itself is recursively structured: trees, nested directories, nested lists or dicts, or divide-and-conquer algorithms like merge sort and binary search.
• Use functools.lru_cache (or a manual dictionary cache) to memoize recursive functions that recompute the same subproblems, such as naive Fibonacci or dynamic-programming style recursions.
• Only raise the limit with sys.setrecursionlimit() as a last resort — it doesn’t increase the actual C stack size, and setting it too high can crash the interpreter instead of raising a catchable RecursionError.
• Add type hints and a short docstring to non-trivial recursive functions; it’s easy to lose track of what shrinks on each call once the logic gets complex.

Practice Exercises

1. Write a recursive function power(base, exponent) that computes base raised to a non-negative integer exponent without using ** or pow(). power(2, 10) should return 1024.
2. Write a recursive function reverse_string(s) that returns a string reversed, without using slicing tricks like s[::-1]. reverse_string("python") should return "nohtyp".
3. Write a recursive function is_palindrome(s) that returns True if a string reads the same forwards and backwards, and False otherwise. is_palindrome("level") should return True and is_palindrome("hello") should return False.

Summary

• Recursion is a function calling itself, split into a base case (stops the recursion) and a recursive case (calls itself on a smaller problem).
• Each call gets its own stack frame; frames are pushed while calls are pending and popped as they return, from the base case back up to the original call.
• CPython has a default recursion limit (around 1000) and no tail-call optimization, so very deep recursion can raise RecursionError or use significant memory.
• Memoization (for example @lru_cache) avoids redundant recomputation in recursive functions with overlapping subproblems, like Fibonacci.
• Every recursive function needs a reachable base case and must actually use the result of its recursive call when one is needed.
• Recursion is most valuable for naturally recursive structures (trees, nested data) and divide-and-conquer algorithms; simple loops are often better for straightforward iteration.