Problem Statement
The task is to generate the nth Fibonacci number using recursion. In the Fibonacci sequence, each number is the sum of the two preceding ones, starting from 0 and 1.
Definition
- Fibonacci sequence: [0, 1, 1, 2, 3, 5, 8, 13, ...]
- The Fibonacci number at index
n is defined as:
fib(0) = 0fib(1) = 1fib(n) = fib(n-1) + fib(n-2), for n > 1.
Example Inputs
Explanation: The Fibonacci sequence for n = 6 is [0, 1, 1, 2, 3, 5, 8], so fib(6) = 8.
Approach - Use Recursion
Approach
Recursion is a method where a function calls itself. In the case of the Fibonacci sequence, we can calculate the nth Fibonacci number by summing the (n-1)th and (n-2)th Fibonacci numbers. This means that for each recursive call, we reduce the problem by one or two indices, until we reach the base cases of fib(0) and fib(1).
Steps
- If
n = 0, return 0.
- If
n = 1, return 1.
- Otherwise, recursively calculate
fib(n-1) + fib(n-2).
- Continue until the base cases are reached.
Time & Space Complexity
- Time Complexity: O(2^n), where
n is the input number. The function makes multiple recursive calls, and the number of calls grows exponentially as n increases.
- Space Complexity: O(n), due to the recursion stack. The maximum depth of the recursion will be
n.
Code Snippet
Dry Run
Let’s dry run the code with the input 6.
- fibonacci(6): fibonacci(5) + fibonacci(4)
- fibonacci(5): fibonacci(4) + fibonacci(3)
- fibonacci(4): fibonacci(3) + fibonacci(2)
- fibonacci(3): fibonacci(2) + fibonacci(1)
- fibonacci(2): fibonacci(1) + fibonacci(0)
- fibonacci(1): 1 (base case)
- fibonacci(0): 0 (base case)
- Return from fibonacci(2): 1 + 0 = 1
- Return from fibonacci(3): 1 + 1 = 2
- Return from fibonacci(4): 2 + 1 = 3
- Return from fibonacci(5): 3 + 2 = 5
- Return from fibonacci(6): 5 + 3 = 8
Output:
Complexity Analysis
Time and Space Complexity
- Time Complexity: O(2^n) because the function makes multiple recursive calls. For each call, two more calls are made until the base cases are reached, which grows exponentially.
- Space Complexity: O(n) due to the recursion stack. Each recursive call consumes space on the call stack, and the maximum depth of the recursion is
n.
Conclusion
Recursion provides a clear and straightforward solution for calculating the nth Fibonacci number. However, the exponential time complexity makes it inefficient for larger values of n. An optimized solution, such as dynamic programming or memoization, can be used to improve performance by storing previously computed results and avoiding redundant calculations.