Fibonacci Number
EasyPrompt
The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.Given n, calculate F(n).
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.
Constraints:
0 <= n <= 30
Approaches
4 approaches with complexity analysis and trade-offs.
This approach directly translates the mathematical definition of the Fibonacci sequence, F(n) = F(n - 1) + F(n - 2), into a recursive function. The function calls itself for n-1 and n-2 and returns their sum. The base cases are F(0) = 0 and F(1) = 1.
Algorithm
- Base Case: If
nis 0 or 1, returnn. - Recursive Step: Otherwise, return
fib(n - 1) + fib(n - 2).
Walkthrough
The algorithm follows the recurrence relation F(n) = F(n-1) + F(n-2). We define a function fib(n). If n is 0 or 1, we return n as these are the base cases. Otherwise, we make two recursive calls: fib(n-1) and fib(n-2) and return their sum. This method is simple to understand but highly inefficient because it recomputes the same Fibonacci numbers multiple times. For example, to calculate fib(5), both fib(4) and fib(3) are called. fib(4) in turn calls fib(3) and fib(2). The value of fib(3) is computed twice, leading to an exponential number of calls.
class Solution { public int fib(int n) { if (n <= 1) { return n; } return fib(n - 1) + fib(n - 2); }}Complexity
Time
O(2^n). For each call to `fib(n)`, we make two more calls, leading to a call tree that grows exponentially. This is very slow.
Space
O(n). The space complexity is determined by the maximum depth of the recursion stack, which is proportional to `n`.
Trade-offs
Pros
Very simple to write and understand.
Directly mirrors the mathematical formula.
Cons
Extremely inefficient due to redundant computations.
Will result in a 'Time Limit Exceeded' error for
ngreater than around 40.
This approach optimizes the brute-force recursion by using a technique called memoization. We store the results of expensive function calls (in this case, fib(k)) in a cache (like an array or hash map) and return the cached result when the same input occurs again. This avoids recomputing the same Fibonacci numbers over and over.
Algorithm
- Create a cache array
memoof sizen+1. - Define a recursive helper function
fib_memo(k). - Base Case: If
k <= 1, returnk. - Memoization Check: If
memo[k]has been computed, return it. - Recursive Step: Otherwise, compute
fib_memo(k-1) + fib_memo(k-2), store the result inmemo[k], and then return it.
Walkthrough
We use an auxiliary array, say memo, of size n+1 to store computed Fibonacci values. We initialize it with a sentinel value (like 0, since Fibonacci numbers are non-negative) to indicate that a value has not been computed yet. The recursive function first checks if the result for n is already in the cache. If it is, it returns the cached value immediately. If not, it computes the value recursively, stores it in the cache, and then returns it. This ensures that each Fibonacci number from 0 to n is computed only once.
class Solution { int[] memo; public int fib(int n) { if (n <= 1) { return n; } // Initialize memoization array. 0 can be used as a sentinel // because fib(k) > 0 for k > 1. memo = new int[n + 1]; return fib_memo(n); } private int fib_memo(int n) { if (n <= 1) { return n; } // Check if the value is already computed if (memo[n] != 0) { return memo[n]; } // Compute and store the value memo[n] = fib_memo(n - 1) + fib_memo(n - 2); return memo[n]; }}Complexity
Time
O(n). Each Fibonacci number from 2 to `n` is computed exactly once. The lookups and stores in the memoization table take constant time.
Space
O(n). We use an array of size `n+1` for the cache, and the recursion stack can also go up to a depth of `n`.
Trade-offs
Pros
Drastically improves time complexity compared to brute-force recursion.
Guarantees that each subproblem is solved only once.
Maintains a top-down, recursive structure that is often intuitive.
Cons
Uses O(n) space for the cache.
Has the overhead of recursive function calls, which can be slightly less performant than a purely iterative solution.
This approach, also known as tabulation, avoids recursion and computes the Fibonacci numbers iteratively from the bottom up. We use an array to store the Fibonacci numbers as we compute them, starting from F(0) and F(1). Each subsequent Fibonacci number F(i) is calculated by summing the two preceding values F(i-1) and F(i-2) which are already available in the array.
Algorithm
- Handle base cases: if
n <= 1, returnn. - Create an array
dpof sizen+1. - Initialize the first two values:
dp[0] = 0anddp[1] = 1. - Loop from
i = 2ton. - In each iteration, calculate
dp[i] = dp[i-1] + dp[i-2]. - Return the last element of the array,
dp[n].
Walkthrough
We create a DP array, say dp, of size n+1 to store the sequence. We seed the array with the base cases: dp[0] = 0 and dp[1] = 1. Then, we iterate from i = 2 up to n. In each step of the loop, we fill dp[i] with the sum of the previous two elements, dp[i-1] + dp[i-2]. The final answer is the value at dp[n]. This approach is generally more efficient in practice than memoization because it eliminates the overhead associated with recursive function calls.
class Solution { public int fib(int n) { if (n <= 1) { return n; } int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; }}Complexity
Time
O(n). We iterate from 2 to `n` once, performing a constant number of operations at each step.
Space
O(n). We allocate an array of size `n+1` to store the intermediate Fibonacci values.
Trade-offs
Pros
Efficient O(n) time complexity.
Avoids recursion overhead, making it slightly faster than memoization in practice.
Conceptually straightforward.
Cons
Uses O(n) space, which is not optimal for this problem.
This is the most optimized version of the bottom-up approach. We notice that to calculate the current Fibonacci number F(i), we only need the two preceding numbers, F(i-1) and F(i-2). There is no need to store the entire sequence in an array. We can simply use two variables to keep track of the last two values and iterate n times to get the final result.
Algorithm
- Handle base cases: if
n <= 1, returnn. - Initialize two variables to represent the first two Fibonacci numbers:
a = 0andb = 1. - Loop from
i = 2ton. - In each iteration, calculate the next Fibonacci number:
sum = a + b. - Update the two variables for the next iteration:
a = bandb = sum. - After the loop,
bwill hold the value ofF(n), so returnb.
Walkthrough
This approach refines the bottom-up strategy by reducing the space complexity to constant. We start with two variables, a = 0 (representing F(0)) and b = 1 (representing F(1)). We then loop from i = 2 to n. In each iteration, we calculate the current Fibonacci number, sum = a + b. Then, we update our variables to slide the window forward for the next iteration: a takes the value of b, and b takes the value of sum. After the loop completes, b will hold the value of F(n). This is the most common and practical solution for this problem.
class Solution { public int fib(int n) { if (n <= 1) { return n; } int a = 0; // Represents F(i-2) int b = 1; // Represents F(i-1) for (int i = 2; i <= n; i++) { int sum = a + b; // Represents F(i) a = b; b = sum; } return b; // b now holds F(n) }}Complexity
Time
O(n). We iterate from 2 to `n` once, performing constant time operations in each iteration.
Space
O(1). We only use a few variables to store the previous two Fibonacci numbers, regardless of the input `n`.
Trade-offs
Pros
Optimal O(1) space complexity.
Efficient O(n) time complexity.
No recursion overhead.
Simple and clean implementation.
Cons
None for the given constraints. This is the optimal solution in terms of both time and space for this problem.
Solutions
Solution
class Solution {public int fib(int n) { int a = 0, b = 1; while (n-- > 0) { int c = a + b; a = b; b = c; } return a; }}/** * @param {number} n * @return {number} */ var fib = function (n) { let a = 0; let b = 1; while (n--) { const c = a + b; a = b; b = c; } return a;};class Solution {public: int fib(int n) { int a = 0, b = 1; while (n--) { int c = a + b; a = b; b = c; } return a; }};class Solution: def fib(self, n: int) -> int: a, b = 0, 1 for _ in range(n): a, b = b, a + b return aVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.