A tree process can repeat the same smaller problem.
Naive Fibonacci branches into overlapping calls, so repeated work grows rapidly 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
- Read finite measurements at their exact observed scope
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 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 precisely record the selected programs and inputs.
- 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 fixed-limit execution trace may stop recording before evaluation stops if the event limit is reached.
Change the program and compare the result.
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 hint
The recursive call counts continue 9, 15, 25, 41, 67, 109 while the iterative process uses n transitions.