用递归算法处理Fibonacci数列问题,计算Fibonacci数列第9项即f(9)的值
时间: 2023-11-21 21:11:45 浏览: 30
好的,根据斐波那契数列的定义,f(0) = 0,f(1) = 1,f(n) = f(n-1) + f(n-2) (n ≥ 2)。那么我们可以写出递归式:
```
int fibonacci(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
```
根据递归式,我们可以算出f(9)的值:
```
fibonacci(9) = fibonacci(8) + fibonacci(7)
= (fibonacci(7) + fibonacci(6)) + (fibonacci(6) + fibonacci(5))
= ((fibonacci(6) + fibonacci(5)) + (fibonacci(5) + fibonacci(4))) + ((fibonacci(5) + fibonacci(4)) + (fibonacci(4) + fibonacci(3)))
= (((fibonacci(5) + fibonacci(4)) + (fibonacci(4) + fibonacci(3))) + ((fibonacci(4) + fibonacci(3)) + (fibonacci(3) + fibonacci(2)))) + (((fibonacci(4) + fibonacci(3)) + (fibonacci(3) + fibonacci(2))) + ((fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))))
= ((((fibonacci(4) + fibonacci(3)) + (fibonacci(3) + fibonacci(2))) + ((fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1)))) + (((fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))) + ((fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0))))) + ((((fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))) + ((fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0)))) + (((fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0))) + ((fibonacci(1) + fibonacci(0)) + (1))))
= (((((fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))) + ((fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0)))) + (((fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0))) + ((fibonacci(1) + fibonacci(0)) + (1)))) + (((((fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0))) + ((fibonacci(1) + fibonacci(0)) + (1))) + (((fibonacci(1) + fibonacci(0)) + (1)) + (1))) + ((((fibonacci(1) + fibonacci(0)) + (1)) + (1)) + (1))))
= (((((2 + 1) + (1 + 0)) + ((1 + 0) + (1 + 0))) + (((1 + 0) + (1 + 0)) + ((1 + 0) + 1))) + (((((1 + 0) + (1 + 0)) + ((1 + 0) + 1)) + (((1 + 0) + 1) + 1)) + (((((1 + 0) + 1) + 1) + ((1 + 0) + 1)) + ((1 + 0) + 1))))
= 34
```
因此,f(9)的值为34。
相关推荐
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)