Algorithms and Data Structures · Junior · Question 28 of 75
Why is this Fibonacci function slow for n = 40?
function fib(n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}- ✓Correct answer: It recomputes the same values again and again
- 2Adding large numbers together is expensive in JS
- 3Recursion in JavaScript is always slower than loops
Explanation
fib(n - 1) and fib(n - 2) both recompute the same smaller values, so the call tree has about 2ⁿ nodes. Caching results (memoization) or a simple loop makes it O(n).