Nth Term of the Fibonacci Sequence
Solve this Problemn, compute the nth Fibonacci number, where fib(0)=0, fib(1)=1, and every later term is the sum of the two before it.
Translating the definition straight into recursion works, but it hides a costly flaw: the same smaller Fibonacci values get recomputed from absolute scratch every time a different branch of the recursion happens to need them again — fib(3) might get fully recalculated two, three, or many more times while computing fib(n) for a larger n, and the redundancy compounds exponentially as n grows. Memoization fixes this without changing the recursive structure at all: cache each answer the first time it's computed, and check the cache before doing any real work. Since there are only n+1 distinct subproblems total, and each now gets solved exactly once, the cost collapses from exponential to linear.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ n ≤ 25 - ◆
fib(0) = 0, fib(1) = 1, and fib(n) = fib(n-1) + fib(n-2) for n ≥ 2
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Plain Recursion — Recompute Every Subproblem
BruteTranslate the definition directly into a recursive function: fib(n) is fib(n-1) plus fib(n-2), with fib(0) and fib(1) as base cases. This is correct, but it recomputes the same smaller values over and over — fib(3), for instance, gets fully recalculated from scratch every single time some larger call happens to need it, and there can be exponentially many such repeats as n grows.
O(2ⁿ)O(n) call-stack space1class Solution {
2 public int nthFibonacci(int n) {
3 if (n <= 1) return n;
4 return nthFibonacci(n - 1) + nthFibonacci(n - 2);
5 }
6}Recursion + Memoization — Cache Each Subproblem's Answer
OptimalKeep the exact same recursive structure, but remember every answer the first time it's computed, in an array indexed by n. Before doing any real work, check whether this n has already been solved — if so, hand back the cached answer immediately instead of recursing again. Since there are only n+1 distinct subproblems total (fib(0) through fib(n)), and each is now computed exactly once, the exponential blowup collapses to linear.
O(n)O(n)1class Solution {
2 public int nthFibonacci(int n) {
3 int[] memo = new int[n + 1];
4 for (int i = 0; i <= n; i++) memo[i] = -1;
5 return helper(n, memo);
6 }
7
8 private int helper(int n, int[] memo) {
9 if (n <= 1) return n;
10 if (memo[n] != -1) return memo[n];
11 memo[n] = helper(n - 1, memo) + helper(n - 2, memo);
12 return memo[n];
13 }
14}