Recursion I

Recursion I | Algoryva

First, the naive way

Loops get awkward with nesting

Suppose you must add up every number in a list that can contain lists, which can contain lists, to any depth: [1, [2, [3, 4]], 5].

A loop handles one level. To handle two levels you need a loop inside a loop; to handle three, another. The depth of the data is not known in advance, so you cannot write enough loops. The data is self-similar, so the code should be too.

python

def total_two_levels(x):
    s = 0
    for item in x:
        if isinstance(item, list):
            for inner in item:        # breaks at depth 3 and beyond
                s += inner
        else:
            s += item
    return s

print(total_two_levels([1, [2, 3], 4]))   # 10

Cost: Correct only for a fixed depth. For unknown depth you would need unlimited nested loops, which is impossible to write.

Worked by hand

Trace factorial(4) by hand

factorial(n) is n × factorial(n − 1), with factorial(0) = 1. The calls go down until the base case, then the answers multiply on the way back up.

phase	call	waiting for	returns
down	factorial(4)	4 × factorial(3)	?
down	factorial(3)	3 × factorial(2)	?
down	factorial(2)	2 × factorial(1)	?
down	factorial(1)	1 × factorial(0)	?
base	factorial(0)	nothing	1
up	factorial(1)		1 × 1 = 1
up	factorial(2)		2 × 1 = 2
up	factorial(3)		3 × 2 = 6
up	factorial(4)		4 × 6 = 24

1
Going down
Nothing is computed yet. Each call just waits, stacked on the previous one, until the base case gives a real number.
2
Coming back up
Each waiting call finishes using the value returned to it. The stack empties in the reverse order it filled.

Implementation

First recursive functions

Every one of these follows the same shape: base case first, then reduce and combine.

Plan in plain steps

pseudocode

solve(problem):
    if problem is tiny: return the known answer      # base case
    smaller = make the problem smaller
    return combine(solve(smaller), this step's work)  # recursive case

python

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

def sum_list(a):
    if not a:
        return 0
    return a[0] + sum_list(a[1:])

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

print(factorial(5))   # 120
print(sum_list([4, 5, 6]))   # 15
print(reverse("abc"))   # cba

Reading the code

›factorial: the base case is n == 0, and the recursive call uses n - 1, which moves toward it.
›sum_list: an empty list sums to 0 (base). Otherwise the first element plus the sum of the rest, which is a shorter list.
›reverse: a string of length 0 or 1 is its own reverse. Otherwise reverse the rest and put the first character at the end.
›a[1:] and s[1:] copy the data, so these teaching versions cost O(n²) time overall. Real code passes an index instead of slicing.

Implementation

Halving the problem: fast exponentiation

Computing x to the power n by multiplying n times is O(n). But x^n is (x^(n/2))² when n is even, so one recursive call on half the exponent does the work of two. When n is odd, pull out one extra factor.

python

def power(x, n):
    if n == 0:
        return 1
    half = power(x, n // 2)
    if n % 2 == 0:
        return half * half
    return half * half * x

print(power(2, 10))   # 1024
print(power(3, 5))   # 243

Reading the code

›We call power only once and reuse half twice. Calling it twice (power(x, n // 2) * power(x, n // 2)) would throw away the speed-up.
›Each call halves n, so the depth is about log₂ n. power(2, 1000000) needs only ~20 levels.
›This “cut the problem in half” shape is also the heart of binary search and merge sort.

Implementation

Many choices: all subsets

For each element you choose to leave it out or take it. The subsets of a list are the subsets of the *rest*, plus those same subsets each with the first element added.

python

def subsets(a):
    if not a:
        return [[]]
    rest = subsets(a[1:])
    return rest + [[a[0]] + r for r in rest]

print(subsets([1, 2]))   # [[], [2], [1], [1, 2]]
print(len(subsets([1, 2, 3, 4])))   # 16

Reading the code

›Base case: the empty list has exactly one subset, the empty one.
›rest holds all subsets without a[0]; the second part is the same sets with a[0] added. Together they cover every case.
›n elements give 2^n subsets, so this cannot be faster than exponential: the output itself is that large.
›This is the seed of backtracking: explore choices recursively, one element at a time.

Worked problem

Flatten a nested list

The problem

Given a list that may contain integers and further nested lists to any depth, return one flat list of all the integers in order.

Base case: if the item is not a list, it is a single value, so its flat form is [item].
Recursive case: for a list, flatten each element and join the results.
The leap of faith: flatten(element) already returns a flat list for that element.

python

def flatten(x):
    if not isinstance(x, list):
        return [x]
    out = []
    for item in x:
        out.extend(flatten(item))
    return out

print(flatten([1, [2, [3, 4]], 5]))   # [1, 2, 3, 4, 5]
print(flatten([]))   # []

Takeaway. When the data has a recursive definition, code that mirrors the definition is shorter and more obviously correct than any loop. Depth of nesting no longer matters.

Worked problem

Tower of Hanoi

The problem

Move n discs from peg A to peg C using peg B as a spare. Only one disc moves at a time and a bigger disc may never sit on a smaller one. List the moves.

To move n discs from A to C: first move the top n − 1 discs out of the way to B.
Then move the largest disc from A to C.
Then move the n − 1 discs from B onto C. The two n − 1 sub-tasks are the same problem with the pegs relabelled.
Base case: zero discs need zero moves.

python

def hanoi(n, src, dst, spare):
    if n == 0:
        return []
    return (hanoi(n - 1, src, spare, dst)
            + [(src, dst)]
            + hanoi(n - 1, spare, dst, src))

print(hanoi(2, "A", "C", "B"))   # [('A', 'B'), ('A', 'C'), ('B', 'C')]
print(len(hanoi(3, "A", "C", "B")))   # 7
print(len(hanoi(10, "A", "C", "B")))   # 1023

Takeaway. Some problems are almost impossible to solve without recursion, yet the solution is three lines. Moves needed are 2^n − 1, which shows recursion can be exponential by the nature of the problem, not by mistake.

Wrap-up

Remember this

A recursive function has a base case and a recursive case that moves toward it.
Trust the smaller call; only show how your answer follows from it.
Calls stack up on the way down and answers combine on the way back up.
Cost is the number of calls and the depth of the stack; naive recursion can repeat subproblems exponentially.
Reach for recursion on nested data, divide-and-conquer, and choice-exploration problems.

Cheat sheet

Shape: if base case: return; else reduce, call, combine
Base case: smallest input with a known answer
Progress: every call must get strictly closer to the base case
Time: number of calls × work per call
Space: call-stack depth (Python limit ≈ 1000)
Halving: depth log n (fast power, binary search)

Top traps to avoid

No base case, or a base case that is never reached.
Recursive call on the same or bigger input.
Forgetting to return the recursive call.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.What happens if a recursive function has no reachable base case?
2.What does sum_list([4, 5, 6]) from the lesson return?
3.power(x, n) by halving has a recursion depth of about:
4.Why does the lesson say to store half = power(x, n // 2) instead of calling it twice?
5.Which task most naturally suggests recursion?
6.How many moves does hanoi(3, "A", "C", "B") produce?
7.What does this print? def f(n): return 1 if n <= 1 else n * f(n-1); print(f(5))
8.What does print(fib(10)) print for def fib(n): return n if n < 2 else fib(n-1) + fib(n-2)?
9.def g(n): return '' if n == 0 else g(n // 2) + str(n % 2). What does print(g(10)) print?
10.calls = []; def h(n): calls.append(n); if n > 0: h(n-1). Then h(2). What is calls?
11.What guarantees that a recursive function stops?
12.def p(n): if n == 0: return; p(n-1); print(n, end=' ') What does p(3) print (ignore the trailing space)?
13.Naive recursive Fibonacci: how many calls does it make, in order of magnitude?
14.What does memoization change in a recursive solution?
15.def s(n): return 0 if n == 0 else n + s(n-1). What does print(s(4)) print?

Recursion I

After this lesson you will be able to

Builds on

Unlocks

Russian nesting dolls

The two parts of every recursive function

Loops get awkward with nesting

A nested list is a number or a list of nested lists

Watch the call stack for fib(4)

Trace factorial(4) by hand

First recursive functions

Reading the code

Halving the problem: fast exponentiation

Reading the code

Many choices: all subsets

Reading the code

Cost of recursion: time and stack space

Edge cases

Mistakes to avoid

How to spot a recursive problem

Flatten a nested list

Tower of Hanoi

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Warm-up2 problems

Core2 problems

Application2 problems

Challenge1 problem