fib(5) calls fib(4) and fib(3), and each of those calls two more, until the base cases fib(1) and fib(0). Every call becomes a node here. Watch how often the same argument comes back: that repetition is the whole cost.
Recursion tree of Fibonacci of 5.
fib(5) is not a base case, so it calls fib(4) first and fib(3) after that.
Call fib(5), which expands into two calls.
fib(4) is not a base case, so it calls fib(3) first and fib(2) after that.
Call fib(4), which expands into two calls.
fib(3) is not a base case, so it calls fib(2) first and fib(1) after that.
Call fib(3), which expands into two calls.
fib(2) is not a base case, so it calls fib(1) first and fib(0) after that.
Call fib(2), which expands into two calls.
fib(1) is a base case: it returns 1 with no further calls, so this node is a leaf.
Base case fib(1).
fib(1) returns 1.
fib(0) is a base case: it returns 0 with no further calls, so this node is a leaf.
Base case fib(0).
fib(0) returns 0.
Both children are back: fib(2) = fib(1) + fib(0) = 1.
fib(2) returns 1.
fib(1) is a base case: it returns 1 with no further calls, so this node is a leaf.
Base case fib(1).
fib(1) returns 1.
Both children are back: fib(3) = fib(2) + fib(1) = 2.
fib(3) returns 2.
fib(2) is not a base case, so it calls fib(1) first and fib(0) after that.
Call fib(2), which expands into two calls.
fib(1) is a base case: it returns 1 with no further calls, so this node is a leaf.
Base case fib(1).
fib(1) returns 1.
fib(0) is a base case: it returns 0 with no further calls, so this node is a leaf.
Base case fib(0).
fib(0) returns 0.
Both children are back: fib(2) = fib(1) + fib(0) = 1.
fib(2) returns 1.
Both children are back: fib(4) = fib(3) + fib(2) = 3.
fib(4) returns 3.
fib(3) is not a base case, so it calls fib(2) first and fib(1) after that.
Call fib(3), which expands into two calls.
fib(2) is not a base case, so it calls fib(1) first and fib(0) after that.
Call fib(2), which expands into two calls.
fib(1) is a base case: it returns 1 with no further calls, so this node is a leaf.
Base case fib(1).
fib(1) returns 1.
fib(0) is a base case: it returns 0 with no further calls, so this node is a leaf.
Base case fib(0).
fib(0) returns 0.
Both children are back: fib(2) = fib(1) + fib(0) = 1.
fib(2) returns 1.
fib(1) is a base case: it returns 1 with no further calls, so this node is a leaf.
Base case fib(1).
fib(1) returns 1.
Both children are back: fib(3) = fib(2) + fib(1) = 2.
fib(3) returns 2.
Both children are back: fib(5) = fib(4) + fib(3) = 5.
fib(5) returns 5.
fib(5) = 5 after 15 calls. The tree roughly doubles with every extra n, so the time is exponential, about 1.6 to the power n, even though only 6 distinct arguments ever appear. Every repeated subtree is wasted work.
Result 5 after 15 calls.