递归求Fabonacci数列
时间: 2023-06-29 15:17:36 浏览: 48
斐波那契数列是一个经典的递归问题,可以使用递归函数来求解。斐波那契数列的前两个数是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。
相关问题
递归求斐波那契数列时间复杂度
递归求斐波那契数列的时间复杂度为O(2^N),其中N为斐波那契数列的项数。这是因为递归求解斐波那契数列的过程中,每个数都需要递归调用前面两个数,因此递归树的深度为N,每个节点都需要计算一次斐波那契数列的值,因此总的计算次数为2^(N-1)。虽然递归求解斐波那契数列具有理论价值,但在实际应用中,不建议使用递归的方式编写较大的斐波那契数列,因为时间复杂度太高,会导致程序运行缓慢。
用递归求斐波那契数列
好的,斐波那契数列是指: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 很大,可能会导致栈溢出等问题。