Python Recursion: Functions and Examples

Working through nested data can leave you unsure how a function should handle each level. Recursion in Python lets a function call itself to solve a problem on a smaller part of its input.

This article explains how recursive calls reach a base case and when to use a loop instead.

TL;DR: Python Recursion

A recursive function calls itself with a smaller or simpler input until a base case returns a result.

• Write a base case that stops making recursive calls.
• Make each recursive call move toward that base case.
• Use a loop for straightforward repetition. Recursion fits naturally nested structures.

What Is Recursion in Python?

Recursion solves a problem by having a function call itself on a smaller part of it. The base case returns directly, while the recursive case reduces the input.

For factorial, the base case returns one for zero. A call with 4 waits for the result from 3, which waits for the result from 2.

Each active call has a frame holding its argument and the point to resume. Python keeps those frames on the call stack. When the base call returns, waiting multiplications run in reverse order and produce 24.

A function that calls itself is direct recursion. In indirect recursion, functions call one another in a cycle. Trace the function name and argument at each call, then follow returns in reverse order.

Here is the same rule in code. I ran the named file with inputs 5 and 0. The captured output is shown beside it.

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))

The output is exactly what the run returned:

120
1

The base case handles zero, while the explicit negative check avoids an unbounded countdown for negative input. The factorial examples page covers other ways to calculate the same value.

How to Write a Recursive Function Step by Step

I use factorial here because each call changes one integer and the stopping input is clear.

Step 1: Choose the base case

Check boundary inputs so invalid values do not enter the call chain.

Step 2: Reduce the problem

For a positive n, multiply n by the answer for n − 1. In the factorial example, an input of 5 leads to arguments 4, 3, 2, 1 and then 0.

Step 3: Combine the returned values

Each waiting frame applies its pending multiplication to the returned value.

When Should You Use Recursion, and What Can Fail?

Recursion fits nested structures such as tree nodes with children. Loops fit repeated counting or accumulation and avoid one function frame per iteration. A loop keeps the changing state in one place for a flat count.

The Python for loop guide covers the loop alternative.

The sys module exposes the current recursion limit, which depends on the running environment and should be queried rather than assumed. Python raises RecursionError when it detects excessive recursive depth. Raising the limit beyond the platform’s safe stack depth can crash the process.

Python does not promise tail-call elimination. A function whose final action calls itself can still use another call frame, so tail-recursive code does not remove the recursion-depth constraint.

Conclusion: Make Progress Toward a Base Case

Trace recursive calls down and their returns back up. If the chain grows too deep, choose an iterative approach or a suitable data structure.

For more practice, see the AskPython guides to Python functions and for loops.

FAQ

These answers cover common questions about recursive calls and Python’s limits.