Exercises — Classic recursion — factorial, Fibonacci, binary search

Base case: if n == 0: … return. Why: it is the only branch that returns without calling countdown again. It is reached when the input has shrunk all the way down to $0$. Without it, countdown(n-1) would keep going to $-1,-2,\dots$ forever → RecursionError.

$s(n)=n+s(n-1),s(0)=0.$ Why $n+s(n-1)$? The total up to $n$ is "$n$ itself" glued onto "the total up to $n-1$" — that is the self-similar structure. Why $s(0)=0$? Summing no numbers gives $0$ (the empty sum), and it stops the chain.

Two base cases: $F_0=0$ and $F_1=1$. Why two? The recurrence $F_n=F_{n-1}+F_{n-2}$ reaches back two steps. If you only anchored $F_0$, then computing $F_1$ would ask for $F_{-1}$ — below the floor — and never stop. You need as many fixed starting values as the number of steps the recurrence looks back.

factorial(4) = 4 * factorial(3)
             = 4 * (3 * factorial(2))
             = 4 * (3 * (2 * factorial(1)))
             = 4 * (3 * (2 * (1 * factorial(0))))
             = 4 * (3 * (2 * (1 * 1)))     # base case 0! = 1
             = 24

Why this order? Every multiplication waits on the call stack until the base case factorial(0)=1 returns, then the products resolve bottom-up: $1,1,2,6,24$. Answer: $24$.

Indices: 2→0, 4→1, 6→2, 8→3, 10→4, 11→5, 14→6. Start lo=0, hi=6.

mid = (0+6)//2 = 3; since $8<11$ the whole left half (indices 0–3) is thrown away. Next mid = (4+6)//2 = 5, and arr[5]==11. Answer: returns index $5$.

Recurrence: $b^n=b\times b^{n-1}$ (one factor of $b$ peeled off), base: $b^0=1$ (empty product).

def power(b, n):
    if n == 0:            # base case: b^0 = 1
        return 1
    return b * power(b, n - 1)   # recursive case

Trace: $2^5=2\cdot 2^4=2\cdot 2\cdot 2^3=\cdots =2\cdot 2\cdot 2\cdot 2\cdot 2\cdot 1=32$. Answer: $32$.

Frames exist for factorial(100), factorial(99), …, factorial(0) — that's every integer from $100$ down to $0$ inclusive: $100-0+1=101$ frames. General: factorial(n) reaches depth $n+1$. Answer for 100: $101$ frames. This is why very large $n$ can trigger RecursionError — Python's default recursion limit is around $1000$ frames.

Recurrence for the counter: one call for fib(n) itself, plus all calls its two children make: $C(n)=1+C(n-1)+C(n-2).$ Building up: $C(2)=1+C(1)+C(0)=1+1+1=3$ $C(3)=1+C(2)+C(1)=1+3+1=5$ $C(4)=1+C(3)+C(2)=1+5+3=9$ $C(5)=1+C(4)+C(3)=1+9+5=15$ Answer: $15$ calls. (Notice $15$ is far more than the $6$ distinct values $F_0\dots F_5$ — the extra $9$ are redundant recomputations. See Big-O Notation.)

Each comparison halves the remaining range, so the worst case is the number of halvings needed to shrink $1000$ down to $1$: $\lfloor {\log }_{2}1000\rfloor +1=9+1=10.$ Check: $2^9=512<1000\le 1024=2^{10}$, so you can halve at most $10$ times. Answer: $10$ comparisons. Compare to linear search's worst case of $1000$ — that gap is the payoff of $\Theta (\log n)$.

Idea: the sum of a list is "its first element" plus "the sum of the rest".

def sum_list(a):
    if len(a) == 0:        # base case: empty list sums to 0
        return 0
    return a[0] + sum_list(a[1:])   # first + sum of the rest

Recurrence: $S(a)=a_0+S(a_{1:})$, base $S([])=0$. Trace: $4+(2+(7+(1+0)))=4+2+7+1=14$. Answer: $14$.

Idea: move the first character to the end, after reversing the rest.

def reverse(s):
    if len(s) <= 1:        # base case: empty or single char is its own reverse
        return s
    return reverse(s[1:]) + s[0]   # reverse the tail, then append the head

Trace:

reverse("cat") = reverse("at") + "c"
               = (reverse("t") + "a") + "c"
               = ("t" + "a") + "c"       # base: "t" reverses to "t"
               = "tac"

Answer: "tac".

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

Trace:

gcd(48,18) = gcd(18, 48%18) = gcd(18, 12)
           = gcd(12, 18%12) = gcd(12, 6)
           = gcd(6,  12%6)  = gcd(6, 0)
           = 6              # base case

Why does it stop? The remainder $a\mathrm{mod}b$ is always strictly smaller than $b$, so b decreases every call and must hit $0$. Answer: $6$.

In Python, a default argument is created once, when the function is defined — not on each call. So the same memo dict is shared across every call that doesn't pass its own.

• Danger: the cache from fib(50) persists into fib(30). Here that's harmless (the cached Fibonacci values are still correct and it even speeds things up), but the same pattern with a list default (e.g. def add(x, box=[])) causes results to leak between calls — a classic bug.
• Safe fix: use memo=None and set if memo is None: memo = {} inside, giving each top-level call a fresh cache while still sharing it down the recursion. Key insight: correctness of memoized fib here survives the shared dict only because Fibonacci values never change; don't rely on that luck in general.

Idea (a Divide and Conquer move): if $n$ is even, $b^n=(b^{n/2}{)}^2$ — compute the half-power once, then square it. If $n$ is odd, $b^n=b\cdot b^{n-1}$.

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

Trace $3^{10}$:

3^10 = (3^5)^2
3^5  = 3 * (3^2)^2
3^2  = (3^1)^2
3^1  = 3 * (3^0)^2 = 3*1*1 = 3

So $3^2=9$, $3^5=3\cdot 9\cdot 9=243$, $3^{10}=243^2=59049$. Recurrence: $T(n)=T(n/2)+O(1)\Rightarrow \Theta (\log n)$ — same shape as binary search. Answer: $3^{10}=59049$.

Start lo=0, hi=4. mid = (0+4)//2 = 2, arr[2] = 5. Since $5<7$, the code assumes everything left of index 2 is smaller and throws it away, searching right with lo=3.

call 1: lo=0 hi=4 mid=2 arr[mid]=5  -> 5<7 -> go right lo=3
call 2: lo=3 hi=4 mid=3 arr[mid]=3  -> 3<7 -> go right lo=4
call 3: lo=4 hi=4 mid=4 arr[mid]=7  -> found, return 4

Here it accidentally found it — but that's luck. If target = 1 (at index 1), the first step $5>1$ would send it left to indices 0–1, where arr is [9,1], and depending on comparisons it may return the wrong index or -1. Why it breaks: the halving logic depends on "left of mid ≤ mid ≤ right of mid", which is exactly the sorted property. Remove that guarantee and eliminating a half is unjustified. Fix: sort first ($\Theta (n\log n)$, see Sorting Algorithms) or use linear search.

L2.1 24 · L2.2 5 · L2.3 32 · L3.1 101 · L3.2 15 · L3.3 10 · L4.1 14 · L4.2 "tac" · L4.3 6 · L5.2 59049