Optimize the code · Easy

Speed Up Recursive Fibonacci

Easy Make it fast Seen at Amazon, Apple

fib(n) returns the n-th Fibonacci number (fib(0) = 0, fib(1) = 1, fib(n) = fib(n - 1) + fib(n - 2)).

The recursive version below matches the definition exactly and is far too slow for n = 40. Make it fast for every n up to 45 without changing the results.

Example 1

Input: n = 10
Output: 55

Example 2

Input: n = 40
Output: 102334155

Constraints

0 <= n <= 45

The slow code

Every case must finish within 300 ms (budgets are per language in the editor).

function fib(n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}

function fib(n: number): number {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}

def fib(n: int) -> int:
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

<?php

function fib(int $n): int
{
    if ($n < 2) {
        return $n;
    }
    return fib($n - 1) + fib($n - 2);
}

class Solution {
    public int fib(int n) {
        if (n < 2) return n;
        return fib(n - 1) + fib(n - 2);
    }
}

Hints

Hint 1

Draw the call tree for fib(5): how many times is fib(2) computed?

Hint 2

Each value depends only on the previous two.

Make it faster

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(1)

Why it is slow: each call makes two more calls, so the call tree has about 1.6^n nodes: over 300 million calls for n = 40, almost all of them recomputing values already computed.

The fix: compute each value once. Either memoize the recursion (a cache keyed by n, O(n) time and space) or, simpler and with no recursion depth risk, iterate keeping only the last two values (O(n) time, O(1) space).

The general lesson interviewers want: overlapping subproblems plus recursion means memoization or bottom-up dynamic programming.

Optimized solution

function fib(n) {
  let [a, b] = [0, 1]; // fib(i), fib(i + 1)
  for (let i = 0; i < n; i++) [a, b] = [b, a + b];
  return a;
}

function fib(n: number): number {
  let a = 0; // fib(i)
  let b = 1; // fib(i + 1)
  for (let i = 0; i < n; i++) [a, b] = [b, a + b];
  return a;
}

def fib(n: int) -> int:
    a, b = 0, 1  # fib(i), fib(i + 1)
    for _ in range(n):
        a, b = b, a + b
    return a

<?php

function fib(int $n): int
{
    [$a, $b] = [0, 1]; // fib(i), fib(i + 1)
    for ($i = 0; $i < $n; $i++) {
        [$a, $b] = [$b, $a + $b];
    }
    return $a;
}

class Solution {
    public int fib(int n) {
        int a = 0, b = 1; // fib(i), fib(i + 1)
        for (int i = 0; i < n; i++) {
            int next = a + b;
            a = b;
            b = next;
        }
        return a;
    }
}

Common mistakes

Memoizing with a cache that is recreated on every call, which caches nothing.
Deep recursion limits (Python's default is 1,000) for larger n: iterate instead.

Follow-up questions

Compute fib(n) mod 1e9+7 for n = 10^18 (matrix exponentiation, O(log n)).
Climbing stairs and house robber use the same pattern.

Speed Up Contains Duplicate · Easy
Speed Up Two Sum · Easy
Speed Up the Most Frequent Word · Easy
Speed Up the Active-Customer Join · Easy
Speed Up Range Sum Queries · Medium
Speed Up Longest Consecutive Sequence · Medium