The Fibonacci recursion tree

Every node is one call to fibonacci(k). Repeated non-base calls are red, while base cases are amber. Move the slider and watch the tree and its redundancy grow by a factor that approaches φ with each step. The total node count is T(n) = 2·F(n+1) − 1, while only n+1 distinct values actually exist.

total calls T(n)
distinct values
redundant calls
result F(n)
computed once recomputed (duplicate) base case