递归求Fabonacci数列
时间: 2023-06-29 09:17:36 浏览: 87
斐波那契数列是一个经典的递归问题,可以使用递归函数来求解。斐波那契数列的前两个数是0和1,从第三项开始,每一项是前两项的和,即:0, 1, 1, 2, 3, 5, 8, 13, 21, ...
下面是使用递归函数求解斐波那契数列的代码:
```
int fibonacci(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
```
这个函数接受一个整数参数n,返回斐波那契数列中第n项的值。当n为0时,返回0;当n为1时,返回1;当n大于1时,返回fibonacci(n-1)加上fibonacci(n-2)的结果,这里fibonacci(n-1)和fibonacci(n-2)就是递归调用自身,分别计算第n-1项和第n-2项的值。
例如,如果调用fibonacci(6),函数会先计算fibonacci(5)和fibonacci(4),然后将它们的结果相加并返回,接着计算fibonacci(5)需要递归计算fibonacci(4)和fibonacci(3),以此类推,最终得到结果8。
相关问题
用递归求斐波那契数列
好的,斐波那契数列是指: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>
int fib(int n) {
if (n <= 1) {
return n;
}
return fib(n-1) + fib(n-2);
}
int main() {
int n;
printf("请输入要求第几个斐波那契数:");
scanf("%d", &n);
printf("第%d个斐波那契数为%d\n", n, fib(n));
return 0;
}
```
阅读全文