Recursion in Python

Mastering Recursion in Python: A Comprehensive Guide

Recursion is when a function calls itself to solve a smaller version of the same problem. It is a powerful technique for problems that are naturally self-similar — factorials, tree traversals, and divide-and-conquer algorithms. In this guide, we’ll explore base cases and recursive cases, build classic recursive functions, look at Python’s recursion limit, and compare recursion with iteration.

What is Recursion?

A recursive function is a function that calls itself. Every recursive solution has two parts:

1. Base case — the simplest input, which the function answers directly without recursing. This stops the recursion.
2. Recursive case — the function calls itself with a smaller or simpler input, moving toward the base case.

Caution

Every recursive function must have a base case. Without one, the function calls itself forever and Python raises RecursionError: maximum recursion depth exceeded.

A First Example: Countdown

countdown.py

def countdown(n):
    if n == 0:           # base case
        print("Liftoff!")
        return
    print(n)
    countdown(n - 1)     # recursive case - smaller input
 
countdown(3)

Output:

command

C:\Users\Your Name> python countdown.py
3
2
1
Liftoff!

Diagram:

diagram recursion call stack mermaid

  graph TD
    A["countdown(3)"] --> B["countdown(2)"]
    B --> C["countdown(1)"]
    C --> D["countdown(0) base case"]
    D --> E["Liftoff! returns"]

How recursive countdown calls stack and unwind

The Factorial Function

The factorial of n (written n!) is the product of all positive integers up to n. It has a natural recursive definition: n! = n * (n-1)!, with 0! = 1 as the base case.

factorial.py

def factorial(n):
    if n == 0 or n == 1:     # base case
        return 1
    return n * factorial(n - 1)   # recursive case
 
print(factorial(5))

Output:

command

C:\Users\Your Name> python factorial.py
120

Here is how the calls expand and then collapse:

factorial(5) expansion

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 Fibonacci Sequence

Each Fibonacci number is the sum of the two before it: fib(n) = fib(n-1) + fib(n-2), with fib(0) = 0 and fib(1) = 1 as base cases.

fibonacci.py

def fib(n):
    if n < 2:             # base cases: fib(0)=0, fib(1)=1
        return n
    return fib(n - 1) + fib(n - 2)
 
for i in range(7):
    print(fib(i), end=" ")

Output:

command

C:\Users\Your Name> python fibonacci.py
0 1 1 2 3 5 8

Tip

Naive recursive Fibonacci recomputes the same values many times and is slow for large n. Cache results with functools.lru_cache to make it fast: add @lru_cache above the function.

Recursion with a Collection: Summing a List

Recursion also works on collections — handle the first item, then recurse on the rest.

sum_list.py

def sum_list(items):
    if not items:            # base case: empty list
        return 0
    return items[0] + sum_list(items[1:])   # first + sum of the rest
 
print(sum_list([1, 2, 3, 4, 5]))

Output:

command

C:\Users\Your Name> python sum_list.py
15

The Recursion Limit

Python limits how deep recursion can go (default around 1000 calls) to prevent a stack overflow from crashing the interpreter. You can inspect and change it.

limit.py

import sys
print(sys.getrecursionlimit())   # default: 1000
sys.setrecursionlimit(2000)      # raise it (use with care)

Caution

Raising the recursion limit too high can crash Python with a real stack overflow. If you need very deep recursion, rewrite the algorithm iteratively instead.

Recursion vs. Iteration

Any recursive solution can be rewritten as a loop, and vice versa. The factorial as a loop:

factorial_iterative.py

def factorial(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result
 
print(factorial(5))   # 120

Recursion	Iteration
Often clearer for self-similar problems (trees, divide & conquer)	Often faster and uses less memory
Uses the call stack — limited depth	No depth limit beyond available memory
Elegant, fewer lines	More explicit state management

Conclusion

Recursion solves a problem by having a function call itself on a smaller input until it reaches a base case. Always define a base case to stop the recursion, and ensure each recursive call moves toward it. Classic examples include factorials, Fibonacci numbers, and list traversals. Remember Python’s recursion depth limit, cache repeated work with lru_cache, and consider iteration when performance or depth matters. For more hands-on examples and in-depth tutorials, explore our resources on Python Central Hub!

---

Try it: Recursion Exercises

Exercise 1 – Factorial

pch.exerciseTag pch.exerciseTitle

Exercise 2 – Sum a List Recursively

pch.exerciseTag pch.exerciseTitle

Exercise 3 – Fibonacci

pch.exerciseTag pch.exerciseTitle