Question
Answer and Explanation
A double recursive sequence is one where each term depends on the previous two terms. Let's consider the Fibonacci sequence as a classic example which can be implemented using recursion. The Fibonacci sequence is defined as follows:
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) for n > 1
Here’s a Python example to calculate the nth Fibonacci number using a double recursive approach:
def fibonacci(n):
if n <= 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
# Example usage:
n = 10
print(f"The {n}th Fibonacci number is: {fibonacci(n)}")
Explanation:
1. Base Cases: The function first checks for the base cases, which are when `n` is 0 or 1. If `n` is 0, it returns 0. If `n` is 1, it returns 1. These base cases are crucial for stopping the recursion.
2. Recursive Step: For `n` greater than 1, the function calls itself twice: once with `n-1` and once with `n-2`. It then returns the sum of these two calls. This is the recursive step that breaks the problem down into smaller subproblems.
3. Example Usage: The example shows how to use the function to calculate the 10th Fibonacci number and prints the result.
Please note that this implementation, while demonstrating double recursion, is not efficient for large values of `n` due to repeated calculations. For better performance, consider using dynamic programming (memoization or tabulation) or an iterative approach.
Here's an example using memoization:
def fibonacci_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 0:
return 0
elif n == 1:
return 1
else:
memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
return memo[n]
# Example usage:
n = 10
print(f"The {n}th Fibonacci number is: {fibonacci_memo(n)}")
In this memoized version, calculated Fibonacci numbers are stored in a dictionary (memo) to avoid redundant calculations. This drastically improves performance for larger inputs.