Python Tutorial › Functions › Recursion

Python Recursion

Q: What is the maximum recursion depth in Python?

The default limit is 1000 frames. sys.getrecursionlimit() shows it. Deep problems should use a loop instead.

IntermediateLesson 27 of 4710 min read10 runnable examples

A recursive function is a function that calls itself to solve a smaller version of the same problem. Recursion is natural for problems with a repeating structure, such as nested folders, trees and many classic interview questions.

In this lesson

The base case and the recursive case
Trace how recursive calls unwind
Avoid the recursion limit
Speed up recursion with memoization

How recursion works

Every recursive function needs two parts:

A base case that answers directly and stops the recursion.
A recursive case that calls the function on a smaller input.

Python

def countdown(n):    if n == 0:              # base case        print("Lift off!")        return    print(n)    countdown(n - 1)        # recursive case: a smaller problem countdown(3)

Output

3
2
1
Lift off!

Factorial

5! means 5 × 4 × 3 × 2 × 1. Notice that 5! = 5 × 4!, which is a recursive definition.

Python

def factorial(n):    if n <= 1:        return 1    return n * factorial(n - 1) print(factorial(5))print(factorial(20))

Output

120
2432902008176640000

Trace the calls

Indenting each call by its depth shows how the calls go down to the base case and the results come back up:

Python

def factorial(n, depth=0):    pad = "  " * depth    print(f"{pad}factorial({n})")    if n <= 1:        result = 1    else:        result = n * factorial(n - 1, depth + 1)    print(f"{pad}-> {result}")    return result factorial(4)

Output

factorial(4)
  factorial(3)
    factorial(2)
      factorial(1)
      -> 1
    -> 2
  -> 6
-> 24

Sum of digits and reversing a string

Python

def digit_sum(n):    if n < 10:        return n    return n % 10 + digit_sum(n // 10) def reverse(text):    if len(text) <= 1:        return text    return reverse(text[1:]) + text[0] print(digit_sum(40721), reverse("python"))

Output

14 nohtyp

Recursion on nested data

Recursion shines when data contains smaller copies of itself, such as lists inside lists:

Python

def flatten(items):    flat = []    for item in items:        if isinstance(item, list):            flat.extend(flatten(item))     # recurse into the sub-list        else:            flat.append(item)    return flat print(flatten([1, [2, [3, 4], 5], [[6]]]))

Output

[1, 2, 3, 4, 5, 6]

The recursion limit

Each call uses memory on the call stack. Python stops runaway recursion with a RecursionError (the default limit is about 1000 calls). A missing base case causes it immediately:

Python

def forever(n):    return forever(n + 1) forever(0)

Output

Traceback (most recent call last):
  File "main.py", line 4, in <module>
    forever(0)
    ~~~~~~~^^^
  File "main.py", line 2, in forever
    return forever(n + 1)
  File "main.py", line 2, in forever
    return forever(n + 1)
  File "main.py", line 2, in forever
    return forever(n + 1)
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Python

import sysprint(sys.getrecursionlimit())

Output

Watch out

Do not just raise the limit with sys.setrecursionlimit() to make a deep recursion work. Rewrite it as a loop instead.

Fibonacci and memoization

The naive Fibonacci function recalculates the same values again and again, so it becomes very slow:

Python

calls = 0def fib(n):    global calls    calls += 1    return n if n < 2 else fib(n - 1) + fib(n - 2) print(fib(20), "calls:", calls)

Output

6765 calls: 21891

functools.lru_cache remembers results, so each value is computed only once:

Python

from functools import lru_cache @lru_cache(maxsize=None)def fib(n):    return n if n < 2 else fib(n - 1) + fib(n - 2) print(fib(80))print(fib.cache_info().misses, "distinct calls")

Output

23416728348467685
81 distinct calls

Recursion or a loop?

Python

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

Output

120 True

	Recursion	Loop
Best for	Trees, nested data, divide-and-conquer	Simple repetition
Readability	Matches recursive definitions	Matches step-by-step thinking
Limits	Recursion depth (about 1000)	None
Speed in Python	Slower (function call overhead)	Faster

Check your understanding

Predict the output

def power(base, exp):    if exp == 0:        return 1    return base * power(base, exp - 1) print(power(2, 10), power(5, 0))

Quick quiz

1. What stops a recursive function from calling itself forever?

2. What error does Python raise for recursion that is too deep?

3. What does @lru_cache do for a recursive function?

Exercise: count files in nested folders

A folder is a dict mapping names to either a file size (int) or another folder (dict). Write a recursive function that returns the total size.

Input

{"a.txt": 10, "img": {"b.png": 200, "old": {"c.png": 50}}, "d.md": 5}

Expected output

Hint 1

If a value is a dict, call the function on it; otherwise add the number.

Python

def total_size(folder):    size = 0    for value in folder.values():        if isinstance(value, dict):            size += total_size(value)        else:            size += value    return size tree = {"a.txt": 10, "img": {"b.png": 200, "old": {"c.png": 50}}, "d.md": 5}print(total_size(tree))

Output

The base case is implicit: a folder with no sub-folders adds up its numbers without recursing. Each sub-folder is handled by the same function.

Program Practice

39 Python Function Programs

Every program has a step-by-step explanation, colour-coded code and its real output.

Start practising →

#1EasyFunction to add two numbers #2EasyPrint a string 10 times #3EasyMultiplication table function #4EasyMaximum of three numbers #5EasySum of a list #6EasyProduct of a list

Related sets:All practice sets