Sponsored
Sponsored
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.
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.
1def fibonacci(n):
2 if n <= 1:
3 return n
4 return fibonacci(n - 1) + fibonacci(n - 2)
5
6n = 4
7print(fibonacci(n))The Python solution defines a recursive function 'fibonacci' to compute the nth Fibonacci number. It checks the base case directly and then induces the recursive call.
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.
Time Complexity: O(n) due to linear iteration.
Space Complexity: O(n) for the array storing Fibonacci numbers.
1using namespace std;
int fibonacci(int n) {
if (n <= 1) return n;
int fib[n+1];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++)
fib[i] = fib[i-1] + fib[i-2];
return fib[n];
}
int main() {
int n = 4;
cout << fibonacci(n);
return 0;
}This C++ solution similarly uses an array to store results. The 'fibonacci' function computes the nth Fibonacci number iteratively by precomputing all required Fibonacci numbers up to n.