Exercises — Recursion depth limit — stack overflow

• A — has a base case n==0 AND each call moves toward it (n-1). Safe for non-negative n within the depth limit. (Note: a negative n would overrun 0 and never stop — the domain assumption matters.)
• B — no base case at all; n grows forever. Always overflows.
• C — has a base case, but C(n) calls C(n) — it never moves toward the base. For any n>0 it always overflows.

Answer: B and C always overflow. A does not (for non-negative n with depth ≤ limit).

boom(0) is frame 1, boom(1) is frame 2, ..., boom(k) is frame $k+1$. The limit of $1000$ allows frames $1$ through $1000$ to exist. Frame $1000$ is boom(999) — that call is allowed. The next call, boom(1000), would be frame $1001$, which exceeds $1000$, so boom(1000) is the call that raises RecursionError. Key off-by-one: the deepest call that succeeds is boom(999) (frame $1000$); the first call that fails is boom(1000) (frame $1001$).

Push order (each waits for the next): depth_sum(4), depth_sum(3), depth_sum(2), depth_sum(1), depth_sum(0). That is $n+1=4+1=5$ frames stacked simultaneously. Only when depth_sum(0) returns 0 do frames start popping (LIFO — last pushed, first popped).

Available depth for your recursion $=1000-12=988$ frames. depth_sum(n) needs $n+1$ frames. Require $n+1\le 988\Rightarrow n\le 987$. Largest safe value: $\mathbf{n}=987$.

Frames needed by recursion: $2000+1=2001$. Total frames on the stack at the deepest point: $2001+30=2031$. So you need the limit to be at least $2031$. sys.setrecursionlimit(2031) is the minimum; in practice you'd pad it (e.g. 3000) for safety.

No. Depth is the longest single chain of paused calls, not the total number of calls. Look at the figure: the tree is wide (many calls) but the deepest path only ever goes down the n-1 branch: fib(10) → fib(9) → fib(8) → ... → fib(1). That path pushes frames for $n=10,9,8,\dots ,1$, so the frames are for $10,9,\dots ,1$ = $10$ frames maximum stacked at once. Total calls is huge ($177$ calls for fib(10)), but they don't all live at the same time — the two branches run one after another, so frames pop between them.

Max depth follows the always-n-1 path: fib(n) → fib(n-1) → ... → fib(1), giving depth $=n$ for $n\ge 1$ (and depth $1$ for $n=0$). Total call count grows roughly like ${\varphi }^n$, where $\varphi \approx 1.618$ is the golden ratio — a fixed constant a bit larger than $1$; raising it to the power $n$ makes the count balloon exponentially as $n$ grows. That is a time/repetition cost, paid sequentially. Depth is a space cost, and only the frames currently paused count. Since the left subtree fully finishes (popping its frames) before the right subtree starts, they never coexist. So depth = $n$ (grows linearly), while call count $\approx {\varphi }^n$ (grows exponentially).

def depth_sum_iter(n):
    total = 0
    while n > 0:
        total += n
        n -= 1
    return total

The loop reuses one frame the whole time, so depth stays $1$ regardless of n. $depth\_sum\_iter(100)=100+99+\cdots +1=\frac{100\cdot 101}{2}=5050$.

def depth_sum(n):
    if n == 0: return 0
    return n + depth_sum(n - 1)
 
def safe_depth_sum(n):
    try:
        return depth_sum(n)
    except RecursionError:
        return None

RecursionError is an ordinary exception (see Exceptions and try-except in Python), so try/except catches it — this is exactly why Python uses a soft, catchable limit instead of a segfault. $safe\_depth\_sum(3)=3+2+1+0=6$.

(a) Total frames alive at the deepest point $=D+k=8000+45=8045$. Minimum limit $=8045$. (b) Stack bytes used $=8045\times 600=4827000$ bytes ($\approx 4.60$ MiB). (c) Available $=8\times 1024\times 1024=8388608$ bytes. Since $4827000<8388608$, yes, it fits — with $8388608-4827000=3561608$ bytes to spare ($\approx 3.40$ MiB). This is the disciplined way to raise the limit: compute the byte budget first (see Memory model — stack vs heap), don't just "crank it to a million."

It is not tail recursion: after depth_sum(n-1) returns, there is still work to do — the addition n + (...). The recursive call is not the last thing that happens, so its frame must stay alive to receive the result and add n. (See Tail recursion and why Python lacks tail-call optimization.) Even a true tail-recursive version (accumulator-style, return helper(n-1, acc+n)) would still overflow in Python, because CPython deliberately keeps every frame (for clean tracebacks) — it has no tail-call optimization. So in Python the fix is the same either way: convert to a loop, giving constant depth $1$. depth_sum_iter(100) = 5050 from L4.1 confirms the loop matches the recursion.

• No Base: a missing OR unreachable base case (including a step that moves away from the base, e.g. a negative input to depth_sum) means no recursive call ever returns.
• Frames Race: because no call returns, no stack frame is ever popped, so the recursion depth climbs by $1$ with every call.
• Stack's out of Space: depth crosses the recursion limit ($\approx 1000$ total frames), and CPython raises a catchable RecursionError before the real, fixed-size stack memory runs out and the OS segfaults.