A folder holds files and other folders, and those folders hold more files and folders. How do you count all the files if you do not know how deep the nesting goes? A for loop has to know in advance what it walks over. But this task has a nice property: counting the files in a subfolder is the same task, only smaller. A function that solves a task by calling itself on a smaller part of it is called recursive. In the lesson «Functions» you learned to define and call functions; now a function will call itself.
RecursionDefinition
A way of solving a problem in which a function calls itself with a smaller or simpler input. Every recursive function has two parts: a base case, answered directly without a new call, and a recursive step, which makes the problem smaller and calls the function again.
Base case and recursive step
The simplest example is a countdown. countdown(3) prints 3 and hands the rest of the work — counting down from 2 — to countdown(2). When n reaches 0, the function prints Start! and stops: that is the base case. Factorial is built the same way: to find 5! we need 4!, for 4! we need 3!, and so on down to 1! = 1.
Where
- n
- a natural number
- n!
- the product 1 · 2 · … · n
The rule repeats the same operation on a smaller number (the recursive step) and gives a value we know without calculating (the base case).
def countdown(n):
if n == 0: # base case
print('Start!')
return
print(n)
countdown(n - 1) # recursive step
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
countdown(3)
print(factorial(5), factorial(10))Expected output
3 2 1 Start! 120 3628800
countdown returns nothing, it only prints; factorial passes its result back to the caller with return.Worked example: unfolding factorial(4)
Problem
Without running the code, compute factorial(4) step by step and say how many calls are made.
Show solutionHide solution
Solution
factorial(3) = 3 · factorial(2)
factorial(2) = 2 · factorial(1)
factorial(1) = 1 — base case, no new call.
Now the results travel back: 2 · 1 = 2, 3 · 2 = 6, 4 · 6 = 24.
There are 4 calls: one for each n = 4, 3, 2, 1.
The call stack and RecursionError
How can one function be running several times at once? Each call gets its own frame: a small area of memory with its own parameters and local variables. Frames are kept on the call stack: a new call goes on top, and when a call finishes with return, its frame is removed and the result goes to the frame below. While factorial(1) runs, factorial(4), factorial(3) and factorial(2) are all waiting on the stack, each with its own n.
Call stackDefinition
The list of function calls that have started but not finished yet, ordered last in, first out. The top frame is the one running now; the others are waiting for its result.
return removes the top frame.def factorial(n, depth=0):
pad = ' ' * depth
print(f'{pad}factorial({n}) called')
if n <= 1:
result = 1
else:
result = n * factorial(n - 1, depth + 1)
print(f'{pad}factorial({n}) returns {result}')
return result
print('answer:', factorial(4))Expected output
factorial(4) called
factorial(3) called
factorial(2) called
factorial(1) called
factorial(1) returns 1
factorial(2) returns 2
factorial(3) returns 6
factorial(4) returns 24
answer: 24The stack is not endless. By default CPython allows about 1000 nested calls (sys.getrecursionlimit() shows the limit). If the base case is missing or never reached, the calls never stop, the limit is hit and Python stops the program with RecursionError: maximum recursion depth exceeded. Below, broken has no base case at all, and also_broken has one, but with an odd n the step n − 2 jumps over 0:
def broken(n):
return n * broken(n - 1) # no base case
def also_broken(n):
if n == 0:
return 0
return n + also_broken(n - 2) # an odd n jumps over 0
for func, arg in ((broken, 5), (also_broken, 6), (also_broken, 7)):
try:
print(func.__name__, arg, '->', func(arg))
except RecursionError:
print(func.__name__, arg, '-> RecursionError')Expected output
broken 5 -> RecursionError also_broken 6 -> 12 also_broken 7 -> RecursionError
also_broken(6) = 6 + 4 + 2 + 0 = 12. With 7 the sequence is 7, 5, 3, 1, −1, … and never meets 0. A safer base case would be if n <= 0.`return` forgotten
def digit_sum(n):
if n < 10:
return n
n % 10 + digit_sum(n // 10)correct
def digit_sum(n):
if n < 10:
return n
return n % 10 + digit_sum(n // 10)return, digit_sum(25) returns None, and for 2026 the program even crashes: one level up Python has to compute 2 + None and raises TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'.Classic tasks: digit sums, Fibonacci, binary search
Many definitions in mathematics are recursive already. The digit sum of a number is its last digit (n % 10) plus the digit sum of the number without that digit (n // 10); a one-digit number is its own digit sum. Fibonacci numbers are defined through the two previous members of the sequence.
Where
- S(n)
- the digit sum of n
- n % 10
- the remainder after division by 10 — the last digit
- n // 10
- integer division — drops the last digit
S(2026) = 6 + S(202) = 6 + 2 + S(20) = 6 + 2 + 0 + S(2) = 10.
Where
- F(n)
- the n-th Fibonacci number
Two base cases are needed because the step looks two members back.
def digit_sum(n):
if n < 10:
return n
return n % 10 + digit_sum(n // 10)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(digit_sum(2026), digit_sum(4096), digit_sum(987654321))
print([fib(n) for n in range(12)])Expected output
10 19 45 [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
Worked examples: predict the result
Problem
1) digit_sum(507); 2) fib(7); 3) how many times is digit_sum called for a 6-digit number?
Show solutionHide solution
Solution
2) F(2) = 1, F(3) = 2, F(4) = 3, F(5) = 5, F(6) = 8, F(7) = 13.
3) Each call drops one digit until a single digit is left: 6 calls for a 6-digit number (k digits — k calls).
The Fibonacci function is short but very slow. Every call makes two more calls, and the same values are computed again and again: fib(5) computes fib(3) twice and fib(2) three times. The number of calls grows almost as fast as the Fibonacci numbers themselves:
Where
- calls(n)
- the number of calls made by the naive
fib(n)
For n = 20: F(21) = 10946, so 2 · 10946 − 1 = 21891 calls — exactly what the program below counts.
from functools import lru_cache
calls = 0
def fib(n):
global calls
calls += 1
return n if n < 2 else fib(n - 1) + fib(n - 2)
for n in (10, 20, 25):
calls = 0
value = fib(n)
print(f'fib({n}) = {value}: {calls} calls')
@lru_cache(maxsize=None)
def fib_cached(n):
return n if n < 2 else fib_cached(n - 1) + fib_cached(n - 2)
def fib_loop(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
print(fib_cached(90), fib_loop(90), fib_cached.cache_info().misses)Expected output
fib(10) = 55: 177 calls fib(20) = 6765: 21891 calls fib(25) = 75025: 242785 calls 2880067194370816120 2880067194370816120 91
lru_cache remembers every result, so fib_cached(90) needs only 91 real calculations (misses) — one for each n from 0 to 90. The loop version keeps just the last two numbers and needs no stack at all. How lru_cache works is explained in the lesson «Decorators and closures».Binary search finds a value in a sorted list by halving the range at every step — each step solves the same task on half the data. We pass the borders lo and hi instead of slicing the list, because every slice would copy the elements.
Empty range
If
lo > hi, the value is not there: return-1(base case).Middle element
mid = (lo + hi) // 2; ifitems[mid] == target, returnmid(base case).Right half
If
items[mid] < target, search the range[mid + 1..hi].Left half
Otherwise search the range
[lo..mid − 1].
def binary_search(items, target, lo=0, hi=None):
if hi is None:
hi = len(items) - 1
if lo > hi: # base case: nothing left
return -1
mid = (lo + hi) // 2
print(f' range [{lo}..{hi}], items[{mid}] = {items[mid]}')
if items[mid] == target: # base case: found
return mid
if items[mid] < target:
return binary_search(items, target, mid + 1, hi)
return binary_search(items, target, lo, mid - 1)
scores = [12, 25, 31, 47, 58, 63, 77, 84, 90, 96]
print('77 at index', binary_search(scores, 77))
print('50 at index', binary_search(scores, 50))Expected output
range [0..9], items[4] = 58 range [5..9], items[7] = 84 range [5..6], items[5] = 63 range [6..6], items[6] = 77 77 at index 6 range [0..9], items[4] = 58 range [0..3], items[1] = 25 range [2..3], items[2] = 31 range [3..3], items[3] = 47 50 at index -1
Interactive
Recursive data: nested lists and folder trees
Recursion feels most natural when the data itself is recursive: lists inside lists, folders inside folders, comments with replies that have replies. The shape of the function follows the shape of the data: an ordinary element is the base case, and for a nested element the function calls itself again.
def total(data):
result = 0
for item in data:
if isinstance(item, list):
result += total(item) # a smaller list of the same kind
else:
result += item
return result
def depth(data):
if not isinstance(data, list):
return 0
return 1 + max((depth(x) for x in data), default=0)
expenses = [120, [30, 45, [5, 5]], 60, [[10], 20]]
print(total(expenses), depth(expenses))
print(total([]), depth([]), depth(7))Expected output
295 3 0 1 0
total adds every number at any depth: 120 + 30 + 45 + 5 + 5 + 60 + 10 + 20 = 295. depth counts the levels of brackets; default=0 takes care of an empty list.A folder tree can be described with nested dictionaries: a key is a name, a number is a file size in KB, and a dictionary is a subfolder. The function prints the tree and returns its size, and every subfolder is handled by the same function one level deeper:
tree = {
'school': {
'math': {'algebra.pdf': 320, 'geometry.pdf': 410},
'photos': {'trip': {'baku.jpg': 2048, 'quba.jpg': 1730}, 'class.png': 960},
'plan.txt': 12,
}
}
def show(folder, indent=0):
size = 0
for name, content in folder.items():
if isinstance(content, dict): # a folder: recurse
print(' ' * indent + name + '/')
size += show(content, indent + 1)
else: # a file: base case
print(' ' * indent + f'{name} ({content} KB)')
size += content
return size
print('Total:', show(tree), 'KB')Expected output
school/
math/
algebra.pdf (320 KB)
geometry.pdf (410 KB)
photos/
trip/
baku.jpg (2048 KB)
quba.jpg (1730 KB)
class.png (960 KB)
plan.txt (12 KB)
Total: 5480 KBNow a real disk. In the pathlib module Path.iterdir() lists the contents of a folder, and is_dir() tells a folder from a file. The program first builds a small project folder (recursively as well), then walks through it and reports the number of files and bytes in every folder:
from pathlib import Path
def make(folder, spec):
for name, content in spec.items():
path = folder / name
if isinstance(content, dict):
path.mkdir()
make(path, content)
else:
path.write_text('x' * content)
def report(folder, indent=0):
files, size = 0, 0
for path in sorted(folder.iterdir()):
if path.is_dir():
f, s = report(path, indent + 1)
print(' ' * indent + f'{path.name}/ files={f}, bytes={s}')
files, size = files + f, size + s
else:
files, size = files + 1, size + path.stat().st_size
return files, size
root = Path('project')
root.mkdir()
make(root, {'docs': {'a.txt': 120, 'b.txt': 80, 'old': {'c.txt': 300}},
'src': {'main.py': 450}, 'readme.md': 50})
print(report(root))
print(sum(p.stat().st_size for p in root.rglob('*') if p.is_file()))Expected output
old/ files=1, bytes=300 docs/ files=3, bytes=500 src/ files=1, bytes=450 (5, 1000) 1000
rglob('*') walks the tree for you and gives the same 1000 bytes: in real scripts rglob and os.walk are the ready-made tools, but inside they do exactly this.Recursion or a loop?
Any recursive function can be rewritten with a loop (with your own stack list if needed), and the other way round. Which one to choose depends on the shape of the task:
| Situation | Better choice | Why |
|---|---|---|
| a simple sequence: the sum 1…n, factorial, a countdown | loop | no stack, no depth limit, usually faster |
| tree-shaped data: nested lists, folders, JSON, HTML | recursion | the code follows the shape of the data |
| divide and conquer: binary search, merge sort, quicksort | recursion | the depth is only about log₂ n |
| the same subproblems again and again (Fibonacci) | recursion + lru_cache, or a loop | every value is computed once |
| the depth can reach thousands of levels | a loop with an explicit stack | no RecursionError |
def sum_rec(n):
return 0 if n == 0 else n + sum_rec(n - 1)
def sum_loop(n):
total = 0
for i in range(1, n + 1):
total += i
return total
print(sum_rec(100), sum_loop(100))
try:
print(sum_rec(100_000))
except RecursionError:
print('sum_rec(100000): RecursionError')
print(sum_loop(100_000))Expected output
5050 5050 sum_rec(100000): RecursionError 5000050000
sum_rec(100000) needs 100 000 frames and fails, while the loop needs none. Python does not optimise tail recursion, so rewriting the function in another recursive form does not help either.Exercise
Write the recursive function power(x, n): xⁿ = x · xⁿ⁻¹ and x⁰ = 1 (n is a whole number ≥ 0). Do not use the ** operator or pow. Keep the three calls of the starter code.
def power(x, n):
# base case: n == 0
# recursive step: x * power(x, n - 1)
pass
print(power(2, 10))
print(power(3, 4))
print(power(5, 0))Expected output
1024 81 1
Exercise
The function count_files(folder) must return the number of files in a nested dictionary: a key whose value is a dictionary is a subfolder, and a key whose value is a number is a file. An empty folder has 0 files.
tree = {
'docs': {'cv.pdf': 120, 'letters': {'a.txt': 4, 'b.txt': 6}},
'music': {},
'photo.jpg': 900,
}
def count_files(folder):
# a dict value is a subfolder, a number is a file
pass
print(count_files(tree))
print(count_files(tree['docs']))
print(count_files(tree['music']))Expected output
4 3 0
Remember
- A recursive function calls itself on a smaller input; it needs a base case and a step that really moves towards it.
- Every call gets its own frame on the call stack; results come back in the reverse order of the calls.
- Without a reachable base case the stack overflows:
RecursionError(about 1000 levels by default in CPython). A step withoutreturngivesNone. - Recursion suits tree-shaped data and divide-and-conquer tasks: nested lists, folder trees, binary search.
- Repeated subproblems →
functools.lru_cache; simple or very deep sequences → a loop.