A recursive Fibonacci function is elegant and unusably slow; the loop version is ugly and instant. Where does the recursive version's time actually go?

C. Into recomputing the same subproblems exponentially often

The tree has about 2ⁿ nodes and only n distinct values in it, so almost all the work is repetition. Adding a cache makes it linear without touching the structure, which is why the fix is memoisation rather than abandoning recursion, and why this is the standard first example of dynamic programming.