用递归求斐波那契数列
时间: 2023-08-04 22:23:59 浏览: 55
好的,斐波那契数列是指:1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... ,其中每一项都是前两项的和。下面是用递归求斐波那契数列的代码示例:
```
int fibonacci(int n) {
if (n == 1 || n == 2) {
return 1;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
```
在这个递归函数中,如果输入的 n 为 1 或 2,则直接返回 1;否则,就递归调用函数本身来求解前两项之和,直到递归到 n=1 或 n=2 为止。需要注意的是,递归算法的时间复杂度较高,如果 n 很大,可能会导致栈溢出等问题。
相关问题
c语言用递归求斐波那契数列防溢出
以下是使用C语言递归求斐波那契数列并防止溢出的示例代码:
```c
#include <stdio.h>
unsigned long long Fib(unsigned long long n) {
if (n <= 2) {
return 1;
} else {
return (Fib(n - 1) + Fib(n - 2));
}
}
int main() {
unsigned long long n;
printf("请输入要计算的斐波那契数列的项数:");
scanf("%llu", &n);
printf("第 %llu 项的斐波那契数为:%llu\n", n, Fib(n));
return 0;
}
```
在上述代码中,我们使用了`unsigned long long`类型来存储斐波那契数列的项数和结果,以防止溢出。`unsigned long long`类型可以存储更大范围的非负整数。
用递归求斐波那契数列n=20
好的,斐波那契数列的定义是:F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n>=2)。
我们可以利用递归函数来求解斐波那契数列,具体实现如下:
```python
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
```
然后,我们可以调用这个函数来计算斐波那契数列的第 20 项,代码如下:
```python
print(fibonacci(20))
```
这样会输出结果 `6765`,即斐波那契数列的第 20 项为 6765。
相关推荐
![](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)