Exercise 3: Why Naive Fibonacci Uses Only O(n) Space — Possible Solution
====================================================================

THE APPARENT PARADOX
------------------------------
Naive recursive Fibonacci makes an exponential number of TOTAL
function calls over its full execution (O(2^n), per Chapter 5's own
analysis) - it might seem like this should also require exponentially
much memory. It doesn't.

WHY TIME AND SPACE MEASURE DIFFERENT THINGS
------------------------------
Per this chapter's own distinction, time complexity counts the TOTAL
amount of work done across the entire execution, adding up every
single call that ever happens. Space complexity, for recursion,
instead measures the MAXIMUM number of call frames sitting on the call
stack AT ANY ONE MOMENT - not the total number of frames that are ever
created over the whole run.

WHY THE CALL STACK NEVER GROWS BEYOND O(n)
------------------------------
Recursion in fib(n) explores depth-first: calling fib(n-1) causes that
entire branch (and everything IT calls) to fully complete and return
before fib(n-2) is even started. This means that at any given instant,
the call stack only ever holds the chain of calls along ONE path from
the original call down to a base case - never two separate branches'
worth of frames stacked up simultaneously. Since each step down that
one path reduces n by at least 1, the longest possible chain has
length proportional to n, giving O(n) maximum stack depth - regardless
of how many total calls eventually happen across the full, much wider
call tree.

WHY THIS WORKS AS AN ANSWER
------------------------------
The explanation is grounded directly in this chapter's own time-vs-
space distinction (total work vs. maximum simultaneous memory) and
explains the mechanism specifically - depth-first recursion only ever
keeps one path's worth of frames on the stack at once - rather than
simply asserting the two complexities differ without explaining why.