Fibo

Problem

Return the n-th Fibonacci number. The sequence starts 0, 1 and every following number is the sum of the previous two: 0, 1, 1, 2, 3, 5, 8, 13, ....

Solution

The textbook recursive definition, translated directly to code:

const fibo = (n: number): number => {
  if (n <= 1) return n;

  return fibo(n - 1) + fibo(n - 2);
};

Complexity Analysis

• Each call branches into two more calls, so the call tree grows exponentially
• The space is the maximum depth of the recursion stack

Notes

• This naive version recomputes the same subproblems over and over: fibo(50) takes noticeable seconds because fibo(48), fibo(47)… are calculated millions of times.
• Two classic fixes worth practicing:
  • Memoization (top-down): cache results by n, dropping the cost to O(n).
  • Iterative (bottom-up): keep only the last two values, O(n) time and O(1) space.
• Good example of why “correct” and “efficient” are different conversations.