A tree process can repeat the same smaller problem.
Naive Fibonacci branches into overlapping calls, so a small answer can require a rapidly growing amount of repeated work while an iterative state process advances once per index.
How can two procedures return the same Fibonacci value while their time and space requirements grow differently?
- Recognize a call tree with overlapping subproblems
- Count recursive applications separately from the returned value
- Track maximum recursive depth as retained process state
- Compare exponential-looking tree growth with linear iterative steps
- Keep finite measurements distinct from a proof about every implementation
The direct fib procedure creates two smaller calls whenever n is at least 2. Those branches overlap: fib 3 appears inside both fib 5 branches, and the same pattern repeats below it. The returned number contains none of that duplicated history, so calls and maximum-depth make the process shape visible.
For n equal to 8, the instrumented tree returns 21 after 67 procedure applications and reaches depth 8. The iterative process carries only two consecutive Fibonacci values plus a remaining counter and reaches the same value in eight transitions. For this textbook pair, naive recursive time grows exponentially while depth grows linearly; iterative time grows linearly while the number of state variables stays constant. The displayed counts still describe only these finite programs and inputs.
(begin
(define calls 0)
(define maximum-depth 0)
(define (record-call! depth)
(set! calls (+ calls 1))
(set! maximum-depth (max maximum-depth depth)))
(define (fib n depth)
(record-call! depth)
(if (< n 2)
n
(+ (fib (- n 1) (+ depth 1))
(fib (- n 2) (+ depth 1)))))
(let ((value (fib 8 1)))
(list value calls maximum-depth)))- Output
- —
- Value
- —
- Diagnostic
- —
The first program returns (21 67 8). The second returns ((4 3 9 4) (5 5 15 5) (6 8 25 6) (7 13 41 7)).
Find each application that splits into n minus 1 and n minus 2, then notice repeated calls with the same smaller n. Compare the rapidly increasing calls field with the iterative steps field, which increases by exactly one for each requested index. The bounded trace may stop recording before evaluation stops if the event limit is reached.
Change the program before you read the hint.
Predict the value, recursive call count, and maximum depth for n equal to 9, then compare them with the iterative step count before running the change.
Show one hint
The recursive call counts continue 9, 15, 25, 41, 67, 109 while the iterative process uses n transitions.