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 <= 30The 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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. |
Recursion for Beginners - Fibonacci Numbers • NeetCode • 27,812 views views
Watch 9 more video solutions →Practice Fibonacci Number with our built-in code editor and test cases.
Practice on FleetCode