Tracing Recursion and Return Values

Part of: Recursion

Following the Values Back Up Many recursive methods combine the result of a smaller call with some local work. To trace them, you must follow values down (as arguments shrink) and back up (as returns combine). The Fibonacci Sequence The Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, ... where each is the sum of the previous two: This has two recursive calls per step, a branching (tree) recursion. To trace fib(4): - fib(4) = fib(3) + fib(2) - fib(3) = fib(2) + fib(1) - fib(2) = fib(1) + fib(0) = 1 + 0 = 1 - fib(1) = 1, fib(0) = 0 Working up: fib(2)=1, fib(3)=fib(2)+fib(1)=1+1=2, fib(4)=fib(3)+fib(2)=2+1=3. Trace Tables A reliable way to trace is a table listing each call and what it returns once its sub-calls resolve. Always resolve the deepest call first, then substitute upward, exactly how the stack unwinds. Watch For Repeated Work Notice fib(2) is computed more than once. Branching recursion can repeat sub-problems, making naive Fibonacci slow for large n. That is fine for tracing practice, but be aware it grows roughly exponentially. Tips for Hand-Tracing - Write the base cases first so you instantly recognize them. - Replace each call with its returned value, innermost first. - Kee

Challenge: Recursive Fibonacci