509. Fibonacci Number - Detailed Explanation

Problem Statement:

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding numbers. By definition, F(0) = 0 and F(1) = 1. For any n > 1, the recurrence is:

[ F(n) = F(n-1) + F(n-2). ]

The problem “Fibonacci Number” asks: given an integer n, calculate the n^th Fibonacci number, F(n).

• Input: An integer n (the position in Fibonacci sequence).
• Output: The value of F(n).

Example Cases:

• Example 1:
  Input: n = 2
  Output: 1
  Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

• Example 2:
  Input: n = 3
  Output: 2
  Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2 .

• Example 3:
  Input: n = 4
  Output: 3
  Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3 .

• Example 4:
  Input: n = 0
  Output: 0
  Explanation: Base case; F(0) is defined to be 0.

• Example 5:
  Input: n = 1
  Output: 1
  Explanation: Base case; F(1) is defined to be 1.

Constraints: n is a non-negative integer with 0 ≤ n ≤ 30 . (Within these constraints, results fit in a 32-bit integer.)

Hints:

• Use the Recurrence: Recognize that Fibonacci numbers are defined by the recurrence relation (F(n) = F(n-1) + F(n-2)). This directly suggests a recursive solution.

• Base Cases: Always handle the smallest cases: F(0) = 0 and F(1) = 1. These stop conditions are crucial in a recursive solution to avoid infinite recursion.

• Overlapping Subproblems: Notice that computing F(n) recursively leads to repeated calculations of the same subproblems. For example, to compute F(5) recursively, you compute F(3) multiple times. Think about how you can store and reuse results of smaller subproblems to avoid repetition (this is the key idea of memoization or dynamic programming).

• Bottom-Up Thinking: Alternatively, consider building the solution from the ground up. If you know F(0) and F(1), you can iteratively compute F(2), then F(3), and so on up to F(n). This is often more efficient than naive recursion.

• Space Optimization: Do you need to store the entire sequence up to F(n)? Perhaps you can get away with storing just a couple of values at a time.

• Advanced Hint: There are mathematical methods to compute Fibonacci faster than O(n). One involves using matrix exponentiation or formulas to achieve O(log n) time. If n were very large, these methods become useful, but they are more complex to implement.

Multiple Approaches:

There are many ways to compute Fibonacci numbers. Below, we discuss five different approaches, from the most straightforward (but least efficient) to more optimized methods, including a mathematically advanced method. We will illustrate each approach with step-by-step reasoning.

Approach 1: Recursive Approach (Naïve)

The most direct implementation follows the Fibonacci definition. We define a function fib(n) that calls itself to compute fib(n-1) and fib(n-2) and returns their sum. This approach is very simple to implement, but highly inefficient for larger n due to repeated calculations.

• Idea: If we need F(n), recursively get F(n-1) and F(n-2), and sum them up. Use the base cases F(0) and F(1) to stop recursion.

• Pseudo-code:

  function fib(n):
      if n <= 1:
          return n
      else:
          return fib(n-1) + fib(n-2)

• Trace Example (n = 5):
  To compute fib(5), the function calls:

  • fib(5)
    ├─ fib(4)
    │ ├─ fib(3)
    │ │ ├─ fib(2)
    │ │ │ ├─ fib(1) ⇒ 1
    │ │ │ └─ fib(0) ⇒ 0
    │ │ └─ fib(1) ⇒ 1
    │ │ (Now fib(2) = 1 + 0 = 1, fib(3) = 1 + 1 = 2)
    │ └─ fib(2) (needs to compute again)
    │ ├─ fib(1) ⇒ 1
    │ └─ fib(0) ⇒ 0
    │ (fib(2) = 1 + 0 = 1)
    │ (Now fib(4) = fib(3) + fib(2) = 2 + 1 = 3)
    └─ fib(3) (needs to compute again)
    ├─ fib(2) ⇒ (will compute as 1)
    └─ fib(1) ⇒ 1
    (fib(3) = 1 + 1 = 2)

  Finally, fib(5) = fib(4) + fib(3) = 3 + 2 = 5.

  Notice that fib(2) and fib(3) were each computed multiple times. This redundancy grows exponentially with n.

• Complexity: This naive recursion has exponential time complexity ~O(2^n). Each call branches into two more calls (except base cases), leading to roughly 2^n calls. The space complexity is O(n) for the recursion call stack (the deepest stack is n calls in the worst case, when unwinding down to F(0)). In practice, this approach is only feasible for small n (which is fine for n ≤ 30 by problem constraints, but not for much larger n).

Approach 2: Memoization (Top-Down Dynamic Programming)

Memoization improves the recursive approach by caching results of subproblems so we don’t recompute them. This is a top-down dynamic programming strategy: we still use recursion, but we remember (memoize) the results of each fib(k) in an array or dictionary after computing it the first time.

• Idea: Maintain a memo (lookup table) for computed Fibonacci values. When fib(n) is called:

  • If the result for n is already in the memo, return it directly (avoiding repeated work).
  • If not, compute fib(n-1) and fib(n-2) recursively, store the sum in the memo, then return it.

• Implementation details: Initialize a memo array of size n+1 (or use a HashMap). You can set memo[0] = 0 and memo[1] = 1 as base cases. For other entries, use -1 or another sentinel to indicate “not computed yet.”

• Trace Example (n = 5):
  Start with memo = {0:0, 1:1} (F(0) and F(1) known).

  1. fib(5) not in memo → compute fib(4) and fib(3).

  2. fib(4) not in memo → compute fib(3) and fib(2).

  3. fib(3) not in memo → compute fib(2) and fib(1).

  4. fib(2) not in memo → compute fib(1) and fib(0) which are base cases 1 and 0. Now we can store memo[2] = 1.

     • Return to fib(3): now compute fib(1) (which is base 1). Store memo[3] = memo[2] + memo[1] = 1 + 1 = 2.

  5. Return to fib(4): now fib(3) is in memo (we just computed memo[3] = 2), so no recursion needed for fib(3); use the memoized value. Compute fib(2) (also memoized as 1). Store memo[4] = memo[3] + memo[2] = 2 + 1 = 3.

  6. Return to fib(5): now compute fib(3) (memo says 2) and fib(4) (memo says 3). Store memo[5] = memo[4] + memo[3] = 3 + 2 = 5.

  The memoization ensures each Fibonacci number from 0 up to 5 was computed only once. Any subsequent calls to those will return instantly from the memo.

• Advantages: We still use recursion, but we avoid duplicate calculations. The recursion tree is effectively pruned into a directed acyclic graph where each F(k) is solved once. This dramatically improves efficiency.

• Complexity: With memoization, the time complexity reduces to O(n) because each number F(2) through F(n) is computed only one time. The space complexity is O(n) for the memo array and O(n) for recursion stack (in the worst case, the recursion depth is n before filling the memo). Given n ≤ 30, this is very efficient. Even for much larger n (say n = 1000), this approach would be feasible in terms of time (though recursion stack might become an issue if n is extremely large, leading to potential stack overflow in some languages).

Approach 3: Iterative Approach (Bottom-Up Dynamic Programming)

Dynamic programming can also be done in a bottom-up manner, which typically uses iteration instead of recursion. We start from the smallest subproblems (the base cases) and build up to the desired n. This avoids the overhead of recursion and is straightforward to implement with a loop.

• Idea: Create an array dp[] of size n+1, where dp[i] will hold F(i). Initialize dp[0] = 0 and dp[1] = 1. Then, for i from 2 to n, compute dp[i] = dp[i-1] + dp[i-2]. Finally, dp[n] will contain the answer.

• Step-by-Step (n = 5):
  Initialize an array dp of length 6 (index 0 through 5).

  • dp[0] = 0 (base case)
  • dp[1] = 1 (base case)
  • i = 2 ⇒ dp[2] = dp[1] + dp[0] = 1 + 0 = 1
  • i = 3 ⇒ dp[3] = dp[2] + dp[1] = 1 + 1 = 2
  • i = 4 ⇒ dp[4] = dp[3] + dp[2] = 2 + 1 = 3
  • i = 5 ⇒ dp[5] = dp[4] + dp[3] = 3 + 2 = 5

  After filling the table up to i=5, dp[5] is 5, which is F(5). We have our answer. We computed each Fibonacci number exactly once in increasing order.

• Memory Usage: This approach uses O(n) space to store the table. For n=30 (max in this problem), that’s trivial. If n were much larger, the array might be a concern, but there's an optimization (next approach) to reduce space.

• Complexity: Time complexity is O(n) (one loop from 2 to n, constant work each iteration). Space complexity is O(n) for the dp array. This is efficient for the given constraints. We also avoid recursion entirely, so there's no risk of stack overflow.

Approach 4: Optimized Iterative Approach (O(1) Space)

On closer observation, the DP table is overkill — at each step we only need the last two Fibonacci values to compute the next one. We can optimize space by keeping just two variables for the previous two Fibonacci numbers and iteratively update them. This yields the same O(n) time complexity but reduces space to constant O(1).

• Idea: Use two variables (say a and b) to track F(i-2) and F(i-1) as we iterate upward. Initially, set a = F(0) = 0 and b = F(1) = 1. Then repeat the following step n−1 times: compute next = a + b (which is F(current index)), update a = b and b = next. After n iterations, b will hold F(n) (or we can use a depending on iteration count – careful indexing is needed, but conceptually one of them holds the answer at end).

• Step-by-Step (n = 5):
  We want to compute F(5). Start with:

  • a = 0 (this will represent F(i-2)), b = 1 (represents F(i-1)). Initially i = 1 (meaning b = F(1)).
    Now loop from i = 2 up to 5, updating:

  1. i = 2: next = a + b = 0 + 1 = 1. Update a = b (a becomes 1), b = next (b becomes 1). (Now a = F(1)=1, b = F(2)=1).

  2. i = 3: next = a + b = 1 + 1 = 2. Update a = b (a becomes 1), b = next (b becomes 2). (Now a = F(2)=1, b = F(3)=2).

  3. i = 4: next = a + b = 1 + 2 = 3. Update a = b (a becomes 2), b = next (b becomes 3). (Now a = F(3)=2, b = F(4)=3).

  4. i = 5: next = a + b = 2 + 3 = 5. Update a = b (a becomes 3), b = next (b becomes 5). (Now a = F(4)=3, b = F(5)=5).

  At this point, for i=5, b = 5 which is F(5). We have our result. Notice how we never needed an array; we just carried forward two values.

  We can summarize these steps in a table for clarity:

  Step (i)	a (prev F)	b (curr F)	next (a+b)
  start	0 (F(0))	1 (F(1))	–
  i = 2	1 (F(1))	1 (F(2))	1
  i = 3	1 (F(2))	2 (F(3))	2
  i = 4	2 (F(3))	3 (F(4))	3
  i = 5	3 (F(4))	5 (F(5))	5

  Table: Iteratively computing Fibonacci. After each step, b holds F(i). At the end, b = 5 which is F(5).

• Complexity: Time complexity is O(n) (still doing n-1 additions). Space complexity is O(1) since we only use a few integer variables. This is the most efficient in terms of memory and more than fast enough for n up to 30 (or even much larger n). In fact, this approach is optimal for linear Fibonacci computation.

• Use cases: This method is typically the go-to solution in interview settings for Fibonacci because it’s simple, uses constant space, and runs in linear time. For example, with this approach computing F(45) (the 45th Fibonacci) takes just a loop of 45 iterations, which is negligible, whereas the naive recursive solution would take on the order of 2^45 ≈ 35 billion calls!

Approach 5: Matrix Exponentiation Approach (Fast Fibonacci Computation)

This approach uses a mathematical property of Fibonacci numbers to achieve a faster computation time, particularly useful if n is very large. Fibonacci numbers can be generated by raising a specific 2×2 matrix to the n^th power. Using fast exponentiation (a divide-and-conquer technique), we can compute this power in O(log n) time.

• Key Idea: The Fibonacci sequence can be encoded in the matrix form:
  [ M = \begin{pmatrix}1 & 1\[6pt]1 & 0\end{pmatrix}. ]
  It turns out that raising M to the n^th power gives:
  [ M^n = \begin{pmatrix}F(n+1) & F(n)\[6pt]F(n) & F(n-1)\end{pmatrix} . ]
  This is a known property of Fibonacci numbers. For example:

  • (M^1 = \begin{pmatrix}1 & 1\1 & 0\end{pmatrix}) yields F(2)=1, F(1)=1 in the top row.
  • (M^2 = \begin{pmatrix}2 & 1\1 & 1\end{pmatrix}) yields F(3)=2, F(2)=1.
  • (M^3 = \begin{pmatrix}3 & 2\2 & 1\end{pmatrix}) yields F(4)=3, F(3)=2.
  • (M^4 = \begin{pmatrix}5 & 3\3 & 2\end{pmatrix}) yields F(5)=5, F(4)=3.
  • (M^5 = \begin{pmatrix}8 & 5\5 & 3\end{pmatrix}) yields F(6)=8, F(5)=5.

  You can see the pattern: the [0,1] entry of (M^n) (or [1,0] entry) is F(n). So if we can efficiently compute (M^n), we get F(n) directly.

• Fast Exponentiation: Computing (M^n) by naive multiplication would be O(n) matrix multiplications, which is not better than the DP approach. Instead, we use exponentiation by squaring (also known as divide-and-conquer power algorithm):

  • If n is even, (M^n = (M^{n/2}) \times (M^{n/2})).
  • If n is odd, (M^n = (M^{\lfloor n/2 \rfloor}) \times (M^{\lfloor n/2 \rfloor}) \times M).

  This way, we recursively halve the power at each step. The number of matrix multiplications will be ~O(log n). Each matrix multiplication is a constant number of operations (multiplying two 2×2 matrices involves about 8 multiplications and 4 additions of numbers, which is constant work). Thus, the overall time is O(log n).

• Example (n = 5): We want to compute (M^5):

  1. n=5 is odd. Compute (M^{\lfloor5/2\rfloor} = M^2) first.
  2. Compute (M^2 = M \times M = \begin{pmatrix}2 & 1\1 & 1\end{pmatrix}) (as above).
  3. Now square that result to get (M^4 = M^2 \times M^2 = \begin{pmatrix}5 & 3\3 & 2\end{pmatrix}).
  4. Since n=5 is odd, multiply (M^4) by one more M: (M^5 = M^4 \times M = \begin{pmatrix}8 & 5\5 & 3\end{pmatrix}).
  5. From (M^5), we read off F(5) as the [0,1] entry which is 5 (or [1,0] entry, also 5). This matches the known F(5).

• Implementation: We implement a fast power function for 2×2 matrices. The steps are:

  1. Define a function to multiply two 2×2 matrices.
  2. Define a recursive (or iterative) function to exponentiate the matrix M to power n:
     • If n == 0, return the identity matrix (\begin{pmatrix}1&0\0&1\end{pmatrix}).
     • If n == 1, return M.
     • Compute halfPower = power(M, n//2).
     • Compute fullPower = halfPower * halfPower (this gives M^{n//2 * 2} = M^{n - (n mod 2)}).
     • If n is odd, do fullPower = fullPower * M (multiply one extra M).
     • Return fullPower.
  3. Use the resulting matrix to get the Fibonacci number (either matrix[0][1] or matrix[1][0] will equal F(n)).

• Complexity: Time complexity is O(log n) for the exponentiation (each level of recursion squares the matrix, reducing the power by half). Space complexity is O(1) for storing a few 2×2 matrices (if using recursion, the call stack is O(log n) deep). For n up to 30, this method is actually overkill (the iterative methods are more than fast enough). But for very large n (hundreds or thousands), matrix exponentiation or similar math techniques become essential.

• Note: There is also a formula using the golden ratio that gives Fibonacci numbers in closed form (known as Binet’s formula). It is (F(n) = \frac{\varphi^n - \psi^n}{\sqrt{5}}), where (\varphi \approx 1.618034) (golden ratio) and (\psi \approx -0.618034) . However, using this in a program is tricky since it involves irrational numbers and can suffer precision errors for large n. The matrix method (or an equivalent fast doubling method) computes exact results using integer arithmetic.

Java Code Implementation:

We provide separate methods for each approach (fibRecursive, fibMemoization, fibDP, fibDPOptimized, fibMatrix).