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 <= 30Problem Overview: The task is to compute the nth Fibonacci number. The sequence starts with F(0) = 0 and F(1) = 1. Every next value is the sum of the previous two: F(n) = F(n-1) + F(n-2). Given an integer n, return the value at that position in the sequence.
Approach 1: Recursive Approach (Time: O(2^n), Space: O(n))
The most direct implementation follows the mathematical definition. Call the function recursively for n-1 and n-2, then add their results. Base cases return 0 for n = 0 and 1 for n = 1. While this version is simple, it recomputes the same subproblems repeatedly. For example, calculating F(5) recomputes F(3) and F(2) multiple times. The recursion tree grows exponentially, which leads to O(2^n) time complexity and O(n) call stack space. This approach mainly demonstrates the structure of the recurrence and basic recursion.
Approach 2: Dynamic Programming (Time: O(n), Space: O(n))
The inefficiency in the recursive solution comes from repeated subproblems. Dynamic programming fixes this by storing previously computed Fibonacci values. Build an array where dp[i] stores F(i). Initialize dp[0] = 0 and dp[1] = 1, then iterate from 2 to n and compute dp[i] = dp[i-1] + dp[i-2]. Each Fibonacci number is calculated once, giving linear time complexity O(n). The array requires O(n) additional space. This method removes redundant computation and is the standard bottom‑up DP solution.
An alternative DP variant uses memoization. Instead of building the table iteratively, recursion stores computed results in a cache. Future recursive calls reuse those values instead of recalculating them. Time complexity becomes O(n), matching the iterative DP approach.
Recommended for interviews: Start by explaining the recursive recurrence to show understanding of the sequence definition. Then move to the dynamic programming solution. Interviewers typically expect the O(n) DP approach because it removes exponential recomputation while keeping the implementation straightforward.
The recursive approach involves directly applying the Fibonacci formula: F(n) = F(n-1) + F(n-2). This approach naturally follows the definition of the Fibonacci sequence, solving subproblems by calling itself. However, this naive implementation leads to overlapping subproblems and higher time complexity.
This recursive solution is easy to implement but inefficient for larger n due to exponential time complexity.
This C program defines a recursive function 'fibonacci' which returns the nth Fibonacci number by recursively calling itself with (n-1) and (n-2) until reaching the base cases of 0 or 1.
Time Complexity: O(2^n) because it grows exponentially, with overlapping subproblems.
Space Complexity: O(n) due to the recursion stack required by function calls.
The dynamic programming approach involves using an array to store previously computed Fibonacci numbers, which prevents redundant calculations found in the recursive approach. This method significantly improves efficiency by transforming the exponential recursive solution into a linear solution, using merely linear space.
In this C solution, an array 'fib' is used to store Fibonacci numbers up to n. The base cases are initialized, and the array is filled iteratively, computing each Fibonacci number from the two preceding numbers, achieving a linear time complexity.
Time Complexity: O(n) due to linear iteration.
Space Complexity: O(n) for the array storing Fibonacci numbers.
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(2^n) because it grows exponentially, with overlapping subproblems. Space Complexity: O(n) due to the recursion stack required by function calls. |
| Dynamic Programming Approach | Time Complexity: O(n) due to linear iteration. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive (Brute Force) | O(2^n) | O(n) | Useful for demonstrating the recurrence relation and understanding recursion trees |
| Dynamic Programming (Bottom-Up) | O(n) | O(n) | Standard interview solution when computing Fibonacci iteratively |
| Memoization (Top-Down DP) | O(n) | O(n) | Good when you want recursion but avoid repeated subproblem computation |
Fibonacci Number | Recur + Memo | Bottom Up | DP Concepts & Qns - 2 | Leetcode-509 • codestorywithMIK • 36,240 views views
Watch 9 more video solutions →Practice Fibonacci Number with our built-in code editor and test cases.
Practice on FleetCode