☕ DSA Java Articles

Topics › Basics › Learn Basic Recursion

Fibonacci Number

Easy TUF ID 381 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

The Fibonacci numbers are defined by F(0) = 0, F(1) = 1, and F(n) = F(n - 1) + F(n - 2) for n ≥ 2. Given n, return F(n).

This is the first recursion problem where the obvious recursive solution is a disaster: it makes two recursive calls per level and recomputes the same values an exponential number of times. Fixing that introduces memoisation, which is the gateway to dynamic programming, and the problem also has a neat O(log n) solution that is worth knowing.

Constraints: 0 ≤ n ≤ 30 on LeetCode (the answer fits in int). We return long so the methods are correct up to n = 92, the largest Fibonacci number that fits in 64 bits.

Example 1

n = 4
answer = 3                // F(4) = F(3) + F(2) = 2 + 1

Example 2

n = 10
answer = 55               // 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

Example 3

n = 0
answer = 0                // base case

Approach 1: Naive recursion

Intuition. Translate the definition directly. The call for n asks for F(n - 1) and F(n - 2) and adds the results. The base cases F(0) = 0 and F(1) = 1 collapse into if (n <= 1) return n.

Algorithm.

  1. If n <= 1, return n.
  2. Otherwise return naiveRecursion(n - 1) + naiveRecursion(n - 2).
static long naiveRecursion(int n) {
    if (n <= 1) return n;                                   // base cases F(0) = 0, F(1) = 1
    return naiveRecursion(n - 1) + naiveRecursion(n - 2);
}

Why it is slow. Draw the call tree for n = 5: F(5) calls F(4) and F(3); F(4) calls F(3) and F(2); and so on. F(3) is computed twice, F(2) three times, F(1) five times. The number of calls grows like the Fibonacci numbers themselves, roughly 1.6^n. For n = 30 that is about 1.6 million calls (fine); for n = 50 it is about 20 billion (not fine).

Complexity. Time O(2^n) (more precisely O(φ^n) with φ ≈ 1.618). Space O(n) for the deepest chain of calls.

Approach 2: Memoised recursion

Intuition. The only problem with Approach 1 is repeated work: there are just n + 1 distinct sub-problems F(0) .. F(n), but the tree has exponentially many nodes. So remember each answer the first time it is computed and return the stored value on every later request. An array memo indexed by n, initialised to -1 (“unknown”), is enough. Every F(k) is now computed exactly once, and the tree collapses to a chain with cheap lookups hanging off it.

Algorithm.

  1. Allocate memo[0..n] filled with -1.
  2. fibMemo(n): if n <= 1, return n. If memo[n] != -1, return it.
  3. Otherwise compute fibMemo(n - 1) + fibMemo(n - 2), store it in memo[n], and return it.
static long memoised(int n) {
    long[] memo = new long[Math.max(n + 1, 2)];
    Arrays.fill(memo, -1);                                  // -1 marks "not computed yet"
    return fibMemo(n, memo);
}

private static long fibMemo(int n, long[] memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    return memo[n];
}

Complexity. Time O(n): each of the n + 1 values is computed once, and every other call is an O(1) lookup. Space O(n) for the memo array plus O(n) for the recursion stack.

Approach 3: Iterative with two variables

Intuition. Memoisation fills the array in the order F(2), F(3), ..., F(n) anyway, so compute it bottom-up with a loop instead. Then notice that F(i) only ever needs the two previous values, so the whole array can shrink to two variables, prev and cur. Each iteration shifts the window one step to the right.

Algorithm.

  1. If n <= 1, return n.
  2. Set prev = 0 (F(0)), cur = 1 (F(1)).
  3. For i from 2 to n: next = prev + cur, prev = cur, cur = next.
  4. Return cur.
static long iterative(int n) {
    if (n <= 1) return n;
    long prev = 0, cur = 1;                                 // F(0), F(1)
    for (int i = 2; i <= n; i++) {
        long next = prev + cur;
        prev = cur;
        cur = next;
    }
    return cur;
}

Dry run on n = 5:

i prev cur next
start 0 1  
2 1 1 1
3 1 2 2
4 2 3 3
5 3 5 5

Return cur = 5, and indeed F(5) = 5.

Complexity. Time O(n), space O(1). This is the answer to give in an interview unless n is enormous.

Approach 4: Fast doubling

Intuition. Two identities let us jump from F(k) and F(k + 1) straight to F(2k) and F(2k + 1):

F(2k)     = F(k) * (2 * F(k + 1) - F(k))
F(2k + 1) = F(k)^2 + F(k + 1)^2

So compute the pair for n / 2 recursively, then derive the pair for n with a handful of multiplications. Halving n at every step gives O(log n) calls. Returning the pair {F(n), F(n + 1)} from each call is the trick that makes the identities usable, because both are needed for the next doubling.

Algorithm.

  1. fibPair(0) returns {0, 1}.
  2. Otherwise get {a, b} = fibPair(n / 2), i.e. a = F(k), b = F(k + 1) with k = n / 2.
  3. Compute c = a * (2b - a) (this is F(2k)) and d = a^2 + b^2 (this is F(2k + 1)).
  4. If n is even, return {c, d}; otherwise return {d, c + d}.
static long fastDoubling(int n) {
    return fibPair(n)[0];
}

/** Returns {F(n), F(n+1)}. */
private static long[] fibPair(int n) {
    if (n == 0) return new long[]{0, 1};
    long[] half = fibPair(n / 2);
    long a = half[0], b = half[1];                          // a = F(k), b = F(k+1) with k = n / 2
    long c = a * (2 * b - a);                               // F(2k)
    long d = a * a + b * b;                                 // F(2k+1)
    if (n % 2 == 0) return new long[]{c, d};                // n = 2k:     {F(2k), F(2k+1)}
    return new long[]{d, c + d};                            // n = 2k + 1: {F(2k+1), F(2k+2)}
}

Check it on n = 3: fibPair(1) uses fibPair(0) = {0, 1} to get c = 0, d = 1, and since 1 is odd returns {1, 1}. Then fibPair(3) has a = 1, b = 1, so c = 1 * (2 - 1) = 1 and d = 1 + 1 = 2; 3 is odd, so it returns {2, 3}, and F(3) = 2 is correct.

Complexity. Time O(log n), space O(log n) for the recursion stack. It only pays off when n is huge and the arithmetic is done modulo a prime or with big integers; for n ≤ 92 the iterative version is just as good.

Edge cases and pitfalls