Skip to content
Python Central Hub

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.

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)
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!
command
C:\Users\Your Name> python countdown.py
3
2
1
Liftoff!

Diagram:

diagram recursion call stack mermaid
How recursive countdown calls stack and unwind

The Factorial Function

The factorial of nn (written n!n!) is the product of all positive integers up to nn. It has a natural recursive definition: n! = n * (n-1)!n! = n * (n-1)!, with 0! = 10! = 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))
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
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
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)fib(n) = fib(n-1) + fib(n-2), with fib(0) = 0fib(0) = 0 and fib(1) = 1fib(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=" ")
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
command
C:\Users\Your Name> python fibonacci.py
0 1 1 2 3 5 8

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]))
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
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)
limit.py
import sys
print(sys.getrecursionlimit())   # default: 1000
sys.setrecursionlimit(2000)      # raise it (use with care)

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
factorial_iterative.py
def factorial(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result
 
print(factorial(5))   # 120
RecursionIteration
Often clearer for self-similar problems (trees, divide & conquer)Often faster and uses less memory
Uses the call stack — limited depthNo depth limit beyond available memory
Elegant, fewer linesMore 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_cachelru_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

Exercise 2 – Sum a List Recursively

Exercise 3 – Fibonacci

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Was this page helpful?

Let us know how we did