Recursion — call stack visualization, base case, recursive case: Exercises

B crashes. a catches n == 0 and returns without recursing, so it stops. b has no if that returns without calling itself — every call makes another call forever → RecursionError: maximum recursion depth exceeded.

Level 2 — Application

Goal: run the machine by hand — trace the winding and unwinding.

Exercise 2.1

Trace fact(4) using

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

Give the final number and the order in which the four calls return.

Recall Solution 2.1

Winding (push): fact(4) → fact(3) → fact(2) → fact(1) → fact(0). Base: fact(0) returns $1$ first (deepest frame, LIFO). Unwinding (pop, multiply on the way up):

fact(1): $1 \cdot 1 = 1$
fact(2): $2 \cdot 1 = 2$
fact(3): $3 \cdot 2 = 6$
fact(4): $4 \cdot 6 = 24$

Return order: fact(0), then fact(1), fact(2), fact(3), fact(4). Answer $= 24$ .

Exercise 2.2

Trace power(2, 3) (compute $2^{3}$ ):

def power(base, exp):
    if exp == 0: return 1
    return base * power(base, exp - 1)

Give the result and how many frames sit on the stack at the deepest point.

Recall Solution 2.2

Descent shrinks exp: $3 \to 2 \to 1 \to 0$ .

power(2,0) = $1$ (base)
power(2,1) = $2 \cdot 1 = 2$
power(2,2) = $2 \cdot 2 = 4$
power(2,3) = $2 \cdot 4 = 8$

Deepest stack: frames for exp = 3, 2, 1, 0 are all alive at once → 4 frames. In general $2^{exp}$ needs exp + 1 frames.

Exercise 2.3

Trace summ([5, 3, 8, 1]) using the list-sum from the parent note. Give the result.

Recall Solution 2.3

Each call peels off the head L[0] and recurses on the tail L[1:]: $5 + (3 + (8 + (1 + base: [] 0)))$ Building back up: $1 + 0 = 1$ , $8 + 1 = 9$ , $3 + 9 = 12$ , $5 + 12 = 17$ . Answer $= 17$ .

Level 3 — Analysis

Goal: reason about depth, break-points, and why order matters.

Exercise 3.1

Python's default recursion limit is about 1000 frames. This function is called as deep(0):

def deep(n):
    if n == 1000: return n
    return deep(n + 1)

Roughly how many frames stack up before it stops, and does it stop or crash?

Recall Solution 3.1

n climbs $0, 1, 2, \dots, 1000$ . It stops at n == 1000 — that's the base case. Frames alive at the deepest point: one for each of $n = 0 \dots 1000$ , i.e. 1001 frames. Because $1001 > 1000$ , this exceeds the default limit and raises RecursionError before reaching the base case. (See Big-O and Recursion Depth — depth, not just correctness, matters.)

Exercise 3.2

The two functions differ only in where print sits. State what each prints for input 3.

def down(n):              # A
    if n < 0: return
    print(n)
    down(n - 1)
 
def up(n):                # B
    if n < 0: return
    up(n - 1)
    print(n)

Recall Solution 3.2

A (down) prints during winding (before the call): 3, 2, 1, 0.
B (up) prints during unwinding (after the call returns): 0, 1, 2, 3.

Why: in B, each frame first fully finishes its child call, and only then runs print(n). The deepest frame (n = 0) unwinds first, so 0 prints first, then 1, and so on back up. Same recursion, mirror-image output.

Exercise 3.3

Does this crash or return? If it returns, what does f(10) give?

def f(n):
    if n == 0: return 0
    return f(n - 2)

Recall Solution 3.3

Starting at 10 and subtracting 2: $10, 8, 6, 4, 2, 0$ → hits the base case n == 0, returns $0$ , and every frame passes that $0$ back unchanged → returns 0. Danger: if called with an odd number like f(9), it would step $9, 7, 5, 3, 1, - 1, - 3, \dots$ and jump past 0 forever → crash. The base case must be reachable by the step size, not just "smaller."

Level 4 — Synthesis

Goal: design your own recursions from a self-similarity insight.

Exercise 4.1

Write a recursive length(L) that returns how many items a list has, without using len(). Then give length([9, 9, 9]).

Recall Solution 4.1

Self-similarity: the length of a list is $1$ (for the head) plus the length of the tail. Base case: the empty list has length $0$ .

def length(L):
    if not L:               # base case
        return 0
    return 1 + length(L[1:])  # recursive case

length([9,9,9]) → $1 + (1 + (1 + 0)) = 3$ .

Exercise 4.2

Write a recursive reverse(s) that reverses a string. Trace reverse("cat").

Recall Solution 4.2

Self-similarity: reversing a string = reverse of its tail, with the head stuck on the end. Base case: an empty string reversed is "".

def reverse(s):
    if s == "":                 # base case
        return ""
    return reverse(s[1:]) + s[0]  # tail reversed, then head at the back

Trace reverse("cat"):

reverse("at") + "c"
(reverse("t") + "a") + "c"
((reverse("") + "t") + "a") + "c"
((("" + "t") + "a") + "c") = "t" + "a" + "c" = "tac" ✅

Exercise 4.3

Write a recursive gcd(a, b) (greatest common divisor) using Euclid's rule $g cd (a, b) = g cd (b, a mod b)$ , with base case $g cd (a, 0) = a$ . Compute gcd(48, 18).

Recall Solution 4.3

Why this recursion: Euclid noticed the gcd of two numbers equals the gcd of the smaller one and the remainder — a strictly smaller pair each step, guaranteeing we reach b == 0.

def gcd(a, b):
    if b == 0:            # base case
        return a
    return gcd(b, a % b)  # recursive case, remainder shrinks

Trace gcd(48, 18):

gcd(48, 18) → gcd(18, 48 % 18 = 12)
gcd(18, 12) → gcd(12, 18 % 12 = 6)
gcd(12, 6) → gcd(6, 12 % 6 = 0)
gcd(6, 0) → base case → returns 6.

Level 5 — Mastery

Goal: combine recursion with tree-shaped or overlapping structure.

Exercise 5.1

fib computes Fibonacci with $fib (0) = 0, fib (1) = 1, fib (n) = fib (n - 1) + fib (n - 2)$ . This is two recursive calls per frame — a tree, not a line. Draw/reason the call tree for fib(4) and give its value and how many times fib(1) is evaluated.

Recall Solution 5.1

The tree branches twice each step (see figure). Values: $fib (4) = 3$ .

Figure — Recursion — call stack visualization, base case, recursive case

Counting the leaves that equal fib(1): expanding fully, fib(1) is reached 3 times and fib(0) 2 times. That repeated work is exactly the "overlapping subproblems" problem — see Fibonacci and overlapping subproblems and its cure, Memoization and Dynamic Programming. $fib (4) = fib (3) + fib (2) = (2) + (1) = 3$

Exercise 5.2

Write a recursive count_nodes(tree) that counts every number in a nested list like [1, [2, 3], [4, [5, 6]]] (each element is either a number or another list). Give the count for that example.

Recall Solution 5.2

Self-similarity: a nested list's count = sum of the counts of its elements; a number counts as $1$ ; a list is counted by the same function (recursion inside the loop). This is the shape of Tree and Graph Traversal.

def count_nodes(x):
    if not isinstance(x, list):   # base case: a plain number
        return 1
    total = 0
    for elem in x:                # recursive case: sum children
        total += count_nodes(elem)
    return total

For [1, [2, 3], [4, [5, 6]]] the numbers are $1, 2, 3, 4, 5, 6$ → 6.

Exercise 5.3

Compare, for fib(20), the number of function calls made by the plain recursion versus a memoized version that stores each answer once. (You don't need the exact plain count — reason about the shape.)

Recall Solution 5.3

Memoized: each distinct fib(k) for $k = 0 \dots 20$ is computed once → about 21 stored results (each further lookup is instant). This is Memoization and Dynamic Programming turning a tree into a line.
Plain recursion: the call tree roughly doubles each level; the exact total number of calls to compute fib(20) is $2 \cdot fib (21) - 1 = 2 \cdot 10946 - 1 = 21891$ calls.

So memoization turns ~21891 calls into ~21 computations — the payoff grows explosively with n. Compare with plain Iteration — for and while loops, which also does it in ~20 steps but without a stack.

Recall Final self-check

Cover the answers and say each aloud. Return order of fact(4)'s calls? ::: fact(0), fact(1), fact(2), fact(3), fact(4). Frames alive at deepest point of power(2,3)? ::: 4 (exp = 3,2,1,0). reverse("cat") = ? ::: "tac". gcd(48,18) = ? ::: 6. fib(4) = ? and how many fib(1) evaluations? ::: 3, and fib(1) is evaluated 3 times. Why does f(n)=f(n-2) crash on odd n but not even? ::: Odd starts skip past the n==0 point; use n<=0 for a reachable range.

Exercises — Recursion — call stack visualization, base case, recursive case

Level 1 — Recognition

Exercise 1.1

Exercise 1.2