fib(n) = fib(n - 1) + fib(n - 2) makes two recursive calls per level. Each of those then makes two more, and so on, producing a call tree whose size roughly doubles at every level, about 2^n calls total to compute fib(n). Worse, the same subproblems are recomputed many times: fib(5) recomputes fib(2) something like five times. The fix is memoization (cache each fib(k) the first time you compute it, reuse it after) which collapses the work to O(n), or convert to a bottom-up loop that fills an array of size n + 1. The Fibonacci example is the canonical illustration of why naive recursion can be catastrophically slow when subproblems overlap, even though the recursive code looks shortest.
Programming Fundamentals · Interview question
Naive recursive Fibonacci is O(2^n). Why?
A strong answer
What a weak answer sounds like
You know the answer. Do you know what gets you dinged?
Pro breaks down the answer most candidates actually give to this question — and the specific reason an interviewer marks it down. It’s the difference between sounding correct and sounding senior, on all 472 questions.
From the lesson
Recursion
A function that calls itself. The base case, the recursive case, the call stack, and the question of when to use recursion vs a loop.