Python, lesson 11
A recursive function is one that calls itself. That sounds like a recipe for an endless loop, but it's a natural way to solve problems that contain smaller copies of themselves: a folder holds folders, a family tree holds smaller family trees, and the sum of a list is the first number plus the sum of the rest.
Each call must move closer to the base case. If it doesn't, the calls never stop.
Most recursive functions return a result that the caller builds on:
Trace factorial(3): it needs factorial(2), which needs factorial(1), which returns 1.
Then the answers flow back up: , then .
2 exercises to try what you just read.
2 * 1 = 23 * 2 = 6Every call that hasn't finished yet waits on the call stack, with its own copy of its local
variables. That's why n doesn't get overwritten as the calls go deeper.
Python limits the depth of the call stack to protect itself; by default the limit is about
1000 calls. Going deeper raises RecursionError. You can inspect the limit with
sys.getrecursionlimit() and raise it with sys.setrecursionlimit(), but if you need tens of
thousands of levels, a loop is usually the better tool. Python does not optimise tail calls,
so recursion is always a little more expensive than a loop.
Recursion shines when the data itself is nested. This function adds up numbers in lists that may contain other lists, to any depth:
Writing that with plain loops would be awkward, because you don't know how deep the nesting goes.
Some recursive functions solve the same small problem many times over. The classic example is
Fibonacci: fib(30) calls fib(28) twice, fib(27) three times, and so on. The number of
calls explodes.
functools.cache fixes this by remembering every result. The second time the function is
called with the same arguments, the stored answer comes straight back:
This technique is called memoisation. It works whenever the function always returns the same output for the same input and its arguments are hashable (numbers, strings, tuples).
Don't try to follow every call in your head. Instead, trust that the recursive call correctly solves the smaller problem, and ask only: "given that answer, how do I finish this one?" Then check that the base case is right and that every call shrinks the input.
The digital root of a number is what you get by adding up its digits, then adding up the digits of that result, and so on until one digit is left. For 9875: 9+8+7+5 = 29, then 2+9 = 11, then 1+1 = 2.
Write two recursive functions: digit_sum(n) returns the sum of the digits of n (use
n % 10 and n // 10), and digital_root(n) uses it until a single digit remains. Read one
non-negative whole number and print its digital root.
Sample input:
Sample output:
You can climb a staircase one or two steps at a time. To reach step n your last move came
either from step n - 1 or from step n - 2, so the number of ways to reach n is
ways(n - 1) + ways(n - 2). There is exactly one way to reach step 0 (stay put) and one way
to reach step 1.
Read n (0 to 90) and print the number of different ways to climb to the top. Large n is
far too slow without a cache, so decorate your function with @cache.
Sample input:
Sample output:
def countdown(n):
if n == 0: # base case
print("Go!")
return
print(n)
countdown(n - 1) # recursive case: a smaller problemdef factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)def deep_sum(items):
total = 0
for item in items:
if isinstance(item, list):
total += deep_sum(item) # a smaller copy of the same problem
else:
total += item
return total
print(deep_sum([1, [2, 3], [[4], 5]])) # 15from functools import cache
@cache
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(90)) # instant9875245