Skip to content
Kuza Ndoto Academy

Recursion

Beginner → IntermediateChapter 5 · Page 30 of 565 min readUpdated 15 Nov 2026

Recursion is when a function calls itself to solve a smaller version of the same problem. It's a natural fit for problems that contain smaller copies of themselves, such as folders inside folders or lists inside lists, and it's a classic topic in programming interviews.

The two essential parts

Every recursive function needs:

  1. A base case: a simple situation where the function returns an answer directly, without calling itself. This is what stops the recursion.
  2. A recursive case: where the function calls itself with a smaller or simpler input, moving closer to the base case.
def countdown(n):
    if n == 0:                 # base case
        print("Liftoff!")
        return
    print(n)
    countdown(n - 1)           # recursive case: a smaller problem

countdown(3)
3 2 1 Liftoff!

countdown(3) prints 3 and calls countdown(2), which prints 2 and calls countdown(1), which prints 1 and calls countdown(0). That call hits the base case and stops.

Factorial: the classic example

The factorial of n, written n!, is n × (n − 1) × … × 1. So 5! = 5 × 4 × 3 × 2 × 1 = 120. Notice that 5! = 5 × 4!, so factorial is defined in terms of a smaller factorial, which makes it perfect for recursion.

def factorial(n):
    if n <= 1:                      # base case: 1! = 1 (and 0! = 1)
        return 1
    return n * factorial(n - 1)     # recursive case

print(factorial(5))
print(factorial(1))
120 1

What happens on the call stack

Each call waits for the one below it to return. Python keeps track of the waiting calls on the call stack. The calls go down until the base case, then the results are multiplied on the way back up:

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
calls (stack grows) return values (stack unwinds) factorial(5) factorial(4) factorial(3) factorial(2) factorial(1) returns 5 * 24 = 120 returns 4 * 6 = 24 returns 3 * 2 = 6 returns 2 * 1 = 2 base case: returns 1
Figure 1. Each call waits on the stack until the one below it returns. Only factorial(1) answers straight away; its result then travels back up, being multiplied at each level until factorial(5) returns 120.

More recursive examples

Adding up a list

The sum of a list is its first item plus the sum of the rest. The sum of an empty list is 0.

def sum_list(numbers):
    if not numbers:                          # empty list
        return 0
    return numbers[0] + sum_list(numbers[1:])

print(sum_list([4, 7, 1]))
12

Reversing a string

def reverse(text):
    if len(text) <= 1:
        return text
    return reverse(text[1:]) + text[0]

print(reverse("Kuza"))
azuK

Where recursion really shines: nested data

When data can be nested to any depth, loops alone struggle, but recursion handles it naturally. This function adds up every number in a list, no matter how deeply lists are nested inside it.

def deep_sum(items):
    total = 0
    for item in items:
        if isinstance(item, list):
            total += deep_sum(item)     # a list inside: recurse
        else:
            total += item
    return total

data = [1, [2, 3], [4, [5, 6]]]
print(deep_sum(data))
21

The same idea is used to walk through folders on a disk, menus with sub-menus and family trees.

Recursion vs. loops

Anything written recursively can also be written with a loop. For factorial, the loop is simple and avoids the overhead of many function calls:

def factorial_loop(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print(factorial_loop(5))
120
RecursionLoops
Elegant for nested or tree-shaped problemsUsually clearer for simple repetition
Each call uses memory on the call stackUses a fixed, small amount of memory
Limited depth in Python (about 1,000 calls by default)Can repeat millions of times

Dangers and limits

Common mistake

A missing or unreachable base case. If the function never stops calling itself, Python eventually raises a RecursionError ("maximum recursion depth exceeded"). For example, countdown(-1) with the code above would never reach n == 0. Using if n <= 0: as the base case is safer. Always check that every recursive call moves closer to the base case.

CPython limits recursion depth to protect your computer from runaway calls. You can check the limit:

import sys
print(sys.getrecursionlimit())
1000

That's the default; it can be raised with sys.setrecursionlimit(), but needing to is usually a sign that a loop would be better.

Repeated work: the Fibonacci trap

In the Fibonacci sequence, each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, …

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print([fib(n) for n in range(10)])
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

This works but is very slow for larger n, because the same values are calculated again and again: fib(50) would make about 40 billion calls. The standard library can remember (cache) results for you:

from functools import cache

@cache
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(50))
12586269025

The @cache line is a decorator; it makes each fib(n) calculate only once, so the answer appears instantly.

Key points

  • A recursive function calls itself on a smaller version of the problem.
  • It must have a base case that stops the recursion, and each call must move towards it.
  • Recursion suits nested, tree-like data; loops are usually better for simple repetition.
  • Python's default depth limit is about 1,000 calls; going deeper raises RecursionError.
  • Avoid repeated work in recursion with caching, such as functools.cache.
Up next · New chapter: Modules & PackagesImporting ModulesUse code from other files and libraries.
→

Tip: use the ← and → keys to move between pages.