14.29 Fibonacci Sequence

14.29.1 Problem Metadata

14.29.2 Description

Compute the n-th Fibonacci number where F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2).

14.29.3 Examples

Input: n = 5
Output: 5

14.29.4 Constraints

  • 0 <= n <= 45

14.29.5 Solution 1 - Top-Down Recursion (Naïve)

14.29.5.1 Walkthrough

Directly apply the recurrence F(n) = F(n-1) + F(n-2) with base cases 0 and 1.

14.29.5.2 Analysis

  • Time Complexity: O(2^n)
  • Space Complexity: O(n) recursion depth

14.29.5.3 Code - Java

public int fibRecursive(int n) {
    if (n <= 1) {
        return n;
    }
    return fibRecursive(n - 1) + fibRecursive(n - 2);
}

14.29.6 Solution 2 - Tail Recursion

14.29.6.1 Walkthrough

Carry two consecutive Fibonacci values forward so each call decrements n until reaching zero. Although still recursive, it avoids repeated subproblems.

14.29.6.2 Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n) recursion depth (unless optimized by compiler)

14.29.6.3 Code - Java

public int fibTail(int n) {
    return fibTailHelper(n, 0, 1);
}

private int fibTailHelper(int n, int a, int b) {
    if (n == 0) {
        return a;
    }
    if (n == 1) {
        return b;
    }
    return fibTailHelper(n - 1, b, a + b);
}

14.29.7 Solution 3 - Bottom-Up DP

14.29.7.1 Walkthrough

Iteratively build Fibonacci numbers from 0 to n, maintaining two running values.

14.29.7.2 Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(1)

14.29.7.3 Code - Java

public int fibIterative(int n) {
    if (n <= 1) {
        return n;
    }
    int prev = 0;
    int curr = 1;
    for (int i = 2; i <= n; i++) {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

14.29.8 Solution 4 - Memoized Recursion

14.29.8.1 Walkthrough

Use a memo array to cache computed Fibonacci numbers, preventing redundant recursion.

14.29.8.2 Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)

14.29.8.3 Code - Java

public int fibMemo(int n) {
    int[] memo = new int[n + 1];
    Arrays.fill(memo, -1);
    return fibMemoHelper(n, memo);
}

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