Classic recursion — factorial, Fibonacci, binary search: Question bank

Intuition How to use this page

This is a concept gym for the parent topic. Every item below targets a misconception or a boundary case — not arithmetic. Read the prompt, say your answer out loud with a reason, then reveal. If your answer was "yes/no" without a why, you haven't really understood it yet.

Before we start, let me re-anchor the words the questions lean on, in plain language:

Base case = the input so small the answer is obvious and needs no further recursion. It is the floor that stops the falling.
Recursive case = the function calling itself on a smaller input and gluing the result together.
Call stack = the computer's hidden pile of "unfinished jobs" — one box (stack frame) per pending call, waiting for the smaller call below it to hand an answer back up.

Keep the mnemonic in mind: "Base, Break, Believe."

First, three symbols this page uses (earn them before you meet them)

Some later answers say things like $Θ (g^{n})$ (for some growth base $g$ we'll pin down) or $T (n) = T (n /2) + c$ . If those look like alien runes, read this section once — then the whole page is self-contained.

True or false — justify

A well-defined recursive algorithm must terminate for every valid input, not merely some.

True. "Terminates for some inputs" is not enough — a correct algorithm must reach a base case on all valid inputs. If even one valid input recurses forever, the algorithm is broken; the "smaller" step must provably approach the base every time.

Factorial's base case could be

1! = 1

instead of

0! = 1

and still work for all

n \geq 1

True for

n \geq 1

, but it breaks on factorial(0) — that call would recurse to factorial(-1) and never stop. Using

0! = 1

covers one more input safely, which is why it's preferred.

fib with only one base case (if n == 0: return 0) still works.

False. fib(1) would compute fib(0) + fib(-1), and fib(-1) recurses forever below zero. The recurrence reaches back two steps, so it needs two known values.

Naive recursive Fibonacci gives wrong answers because it's slow.

False. It gives perfectly correct answers — it is only wasteful, recomputing the same subproblems exponentially. Slowness and incorrectness are different failures; here only speed is wrong.

Binary search returns the smallest index of the target when duplicates exist.

False (as written). The middle-first logic can land on any matching copy; it returns some valid index, not guaranteed the leftmost. Finding the first occurrence needs an extra "keep searching left" tweak.

Every recursive function can be rewritten as a loop.

True — see Recursion vs Iteration. Any recursion can be simulated with an explicit stack and a loop; the machine already does this with its own call stack.

Memoizing factorial gives the same speedup as memoizing Fibonacci.

False. Factorial's calls never repeat a subproblem — factorial(n) calls factorial(n-1) exactly once each — so caching adds overhead with zero benefit. Fibonacci repeats subproblems, which is why memoization helps it.

Binary search on an unsorted list always returns

- 1

False. It may return a wrong index or miss a present element — the "throw away a half" logic is simply invalid on unsorted data, so results are unreliable, not uniformly

- 1

The Fibonacci call tree — why $Θ (φ^{n})$ , seen and derived

Formula The characteristic-equation derivation (with its base cases)

Let $C (n)$ = the total number of fib calls made to evaluate fib(n). State the initial conditions first, because a recurrence is meaningless without them: the base-case calls fib(0) and fib(1) each do exactly one call (themselves, no recursion), so $C (0) = 1, C (1) = 1.$ For $n \geq 2$ , evaluating fib(n) is one call for itself plus all the calls its two children make: $C (n) = this call 1 + C (n - 1) + C (n - 2) .$ Now, why we may drop the $+ 1$ for the growth-rate question. The homogeneous part $C (n) = C (n - 1) + C (n - 2)$ already grows exponentially; the extra $+ 1$ per node adds at most a total proportional to the number of nodes, which is itself of the same exponential order. Adding a quantity of the same order (or smaller) never changes the exponential base — it only rescales by a constant factor, and $Θ (\cdot)$ ignores constant factors. So the base is decided purely by the homogeneous recurrence. Guess a solution $C (n) = x^{n}$ and plug in: $x^{n} = x^{n - 1} + x^{n - 2} .$ Divide through by $x^{n - 2}$ (the characteristic equation): $x^{2} = x + 1 ⟹ x^{2} - x - 1 = 0.$ The positive root is $x = \frac{1 + 5}{2} = φ \approx 1.618$ — the golden ratio we met above. So the call count grows like $φ^{n}$ , giving runtime $Θ (φ^{n})$ . Because $1.618 < 2$ , this is smaller than $2^{n}$ but far larger than any polynomial.

Why is naive Fibonacci

Θ (φ^{n})

and not

Θ (2^{n})

Because the call tree is lopsided — one child is fib(n-1), the other only fib(n-2) — so leaves multiply by

φ \approx 1.618

per level, not by

2

. The characteristic equation

x^{2} = x + 1

pins the growth base to the golden ratio

φ

Spot the error

def factorial(n):
    return n * factorial(n - 1)

Why is this wrong?

There is no base case. It recurses forever (below zero too), triggering RecursionError: maximum recursion depth exceeded. Every recursion needs a floor.

def factorial(n):
    if n == 0:
        return 1
    return factorial(n - 1)      # forgot the "n *"

What does this return for any

n

, and why?

Always 1. It recurses down to the base and returns 1 without ever multiplying by n — the "combine" step of the recursive case is missing, so no actual product is built.

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 1)   # both terms n-1

Why is this wrong?

The recurrence must be

F_{n - 1} + F_{n - 2}

, not

F_{n - 1} + F_{n - 1}

. This computes

2^{n - 1}

instead of Fibonacci — right shape of recursion, wrong subproblem.

def binary_search(arr, target, lo=0, hi=None):
    if hi is None: hi = len(arr)      # should be len(arr) - 1
    ...
    mid = (lo + hi) // 2
    if arr[mid] == target: return mid
    elif arr[mid] < target: return binary_search(arr, target, mid + 1, hi)
    else: return binary_search(arr, target, lo, mid - 1)

Trace the full control flow: what actually goes wrong when target exceeds every element?

With hi = len(arr) the range includes the invalid index len(arr). As the search keeps going right, mid climbs toward len(arr); the moment mid == len(arr), arr[mid] reads past the end → IndexError. (If the target is present, it may return the right index by luck first — the bug only bites on the right-edge path, which is exactly why off-by-one range bugs are so sneaky.)

def binary_search(arr, target, lo, hi):
    mid = (lo + hi) // 2
    if arr[mid] < target:
        return binary_search(arr, target, mid, hi)   # mid, not mid+1
    ...

Why can this loop forever?

When lo and hi are adjacent, mid == lo, and recursing with lo = mid (not mid + 1) never shrinks the range. The problem must get strictly smaller each call.

def fib(n, memo={}):
    memo[n] = fib(n-1) + fib(n-2)    # base case check missing
    return memo[n]

Why does memoization not save this version?

The base case check is gone, so it recurses below zero forever before any cache entry helps. Memoization speeds a correct recursion; it can't rescue a missing base case.

Using a mutable default argument def fib(n, memo={}) — what subtle trap does it carry?

The {} is created once and shared across all calls, even between separate top-level invocations. Cached values persist (usually fine here, but surprising) — a classic Python gotcha worth knowing.

Binary search intervals — watch the window shrink

Why questions

Why does the multiplication in factorial(n) happen after the recursive call returns, not before?

Because n * factorial(n-1) must wait for factorial(n-1) to produce a value first. Each pending multiply sits on the call stack and only fires as the stack unwinds from the base up.

Why does memoization turn

Θ (φ^{n})

into

Θ (n)

Each distinct

F_{k}

for

k = 0 \dots n

is computed exactly once and stored; later requests are

O (1)

lookups. Work becomes proportional to the number of unique subproblems, which is

n

. See Memoization and Dynamic Programming.

Why does binary search need the list sorted, precisely?

Sorted order is what makes "everything left of mid is smaller, everything right is bigger" true — that single fact is what lets one comparison safely discard a whole half. Remove sortedness and the half you throw away might contain the target.

Why is binary search a Divide and Conquer algorithm but factorial is not?

Divide and conquer splits the problem into parts and combines them; binary search halves the search space. Factorial only reduces by one each step (linear chain), so it's plain recursion, not divide-and-conquer.

Why does the recurrence

T (n) = T (n /2) + c

solve to

Θ (lo g_{2} n)

First fix its base case: a problem of size

1

takes a constant amount of work,

T (1) = c

(one comparison, no further recursion). Now unroll:

T (n) = c + T (n /2) = c + c + T (n /4) = \dots = k \cdot c + T (n / 2^{k})

. The recursion stops when the size hits

1

, i.e.

n / 2^{k} = 1 \Rightarrow k = lo g_{2} n

, and there

T (1) = c

. So total work

\approx (lo g_{2} n + 1) c = Θ (lo g_{2} n)

— you can only halve

n

that many times.

Why can excessive recursion depth crash even a correct recursion?

Every pending call holds a stack frame, and the call stack has a finite limit (Python's default is ~1000). Deep-but-valid recursion (e.g. factorial(5000)) overflows it → RecursionError.

Edge cases

What does correct factorial(0) return, and why is that not "nothing"?

It returns 1. An empty product is defined as 1 — forced by the pattern

0! = 1! /1 = 1

(see the opening figure) — and it also serves as the base that halts recursion.

What do fib(0) and fib(1) return, and why must both be hard-coded?

0 and 1 respectively. They are the two seeds the recurrence reaches back to; without both, fib(1) would try to use the nonexistent fib(-1).

Binary search on an empty list [] — what happens?

hi = len(arr) - 1 = -1, so lo (0) > hi (-1) is immediately true → returns -1 (not found). The empty-range base case handles it cleanly.

Binary search for a target smaller than every element — trace the shrink.

Each comparison finds arr[mid] > target, so hi keeps moving left until lo > hi → returns -1. It never spins; the range strictly shrinks to empty.

Binary search on a single-element list [5] searching for 5 vs 3.

For 5: lo=hi=0, mid=0, arr[0]==5 → returns 0. For 3: arr[0]=5>3 → hi=-1, then lo>hi → returns -1. Both terminate in one or two steps.

What is factorial(-1) with the standard if n == 0 base — safe or not?

Not safe. It never hits n == 0, recursing

- 1, - 2, - 3, \dots

forever → RecursionError. Negative inputs are outside the definition and should be rejected up front.

For binary search, what if the list has duplicate targets — is the result deterministic?

Yes, deterministic for a fixed list: the same mid sequence runs every time, returning the same index. But it isn't guaranteed to be the first or last duplicate — just a valid one.

What is the smallest

n

where naive fib(n) noticeably lags, and why does it appear so suddenly?

Around fib(35)–fib(40). Because cost grows as

φ^{n}

, each extra

n

multiplies work by ~1.6 — the slowdown feels sudden precisely because exponential growth stays cheap then explodes.

Recall One-line self-test

Cover the answers above. Can you, for each of the four failure modes — missing base case, wrong subproblem, off-by-one range, unsorted input — name the exact symptom it produces (infinite recursion / RecursionError, a wrong value, an IndexError or endless loop, and unreliable results)? If you can pair every failure with its symptom without peeking, you own this topic.

Connections

Recursion vs Iteration — every trap here has a loop-based analogue
Big-O Notation — the $φ^{n}$ vs $lo g n$ reasoning and $Θ$ notation
Memoization and Dynamic Programming — the fix for repeated subproblems
Divide and Conquer — why binary search halves and factorial doesn't
The Call Stack and Stack Frames — the source of RecursionError
Sorting Algorithms — the precondition binary search silently assumes