Mastering Python Recursion: How Functions Call Themselves

Mastering Python Recursion

Discover how Python functions can call themselves, the mechanics of recursion, and best practices for writing safe, efficient recursive code.

What Is Recursion?

Recursion is the technique of defining a problem in terms of a smaller instance of the same problem.

A classic illustration involves two parallel mirrors facing each other; each image is a recursive reflection of the other.

Python Recursive Function

In Python, a function can invoke other functions, and it can even invoke itself. Such constructs are called recursive functions.

The image below demonstrates the call stack for a simple recursive function named recurse:

Below is a classic example: a recursive implementation of the factorial function, which returns the product of all positive integers up to x.

Example of a Recursive Function

def factorial(x):
    """Recursively compute the factorial of a positive integer."""
    if x == 1:
        return 1
    return x * factorial(x - 1)

num = 3
print("The factorial of", num, "is", factorial(num))

Output

The factorial of 3 is 6

Here, factorial() is a recursive function because it calls itself until the base case x == 1 is reached.

When invoked with a positive integer, the function repeatedly calls itself with a decremented value:

factorial(3)          # 1st call with 3
3 * factorial(2)      # 2nd call with 2
3 * 2 * factorial(1)  # 3rd call with 1
3 * 2 * 1             # return from 3rd call
3 * 2                 # return from 2nd call
6                     # return from 1st call

Below is a visual representation of this step‑by‑step process:

The recursion terminates when the input value reaches the base condition (in this case, x == 1). Every recursive function must include such a stopping criterion; otherwise, it would continue indefinitely and eventually exhaust the call stack.

Python enforces a maximum recursion depth (default 1000) to prevent infinite recursion from crashing the interpreter. Exceeding this limit raises a RecursionError:

def recursor():
    recursor()
recursor()

Output

Traceback (most recent call last):
  File "<string>", line 3, in <module>
  File "<string>", line 2, in a
  File "<string>", line 2, in a
  File "<string>", line 2, in a
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

You can adjust the recursion limit programmatically using sys.setrecursionlimit(), but do so with caution to avoid stack overflow.

Advantages of Recursion

1. Recursive solutions are often more concise and easier to read, especially for problems naturally expressed in recursive terms.
2. They enable elegant decomposition of complex tasks into simpler sub‑problems.
3. Sequence generation (e.g., Fibonacci, permutations) is straightforward with recursion compared to nested loops.

Disadvantages of Recursion

1. Recursive logic can be harder to follow and reason about for beginners.
2. Each recursive call consumes stack space; deep recursions can be memory‑intensive and slower than iterative alternatives.
3. Debugging recursion can be challenging because of the layered call stack.

In practice, choose recursion when it leads to clearer, more maintainable code and when the input size is moderate. For very large inputs, iterative approaches or tail‑recursion optimizations (when supported) may be preferable.