c语言 递归书写斐波那契数列

斐波那契数列是指从第三项开始，每一项都等于前两项之和的数列。在C语言中，可以使用递归的方式来求解斐波那契数列。递归函数fun(n)的终止条件是n等于1或2，此时返回1；否则返回fun(n-1)+fun(n-2)。在主函数中，通过循环调用fun函数来打印出前n项斐波那契数列。

需要注意的是，引用中的代码存在一些错误。在引用中，for循环中的fun(i)应该改为fib(i)；在引用中，函数fun的调用应该改为fib。

相关问题

c语言递归实现斐波那契数列代码

下面是C语言递归实现斐波那契数列的代码：

#include <stdio.h>

int fun(int n) {
    if(n == 1 || n == 2) {
        return 1;
    } else {
        return fun(n-1) + fun(n-2);
    }
}

int main() {
    int i, n;
    printf("请输入你要打印的斐波那契数列项数:\n");
    scanf("%d", &n);
    printf("斐波那契数列:");
    for(i = 1; i <= n; i++) {
        printf("%d ", fun(i));
    }
    return 0;
}

该代码通过递归的方式实现了斐波那契数列的求解，其中fun函数用于递归求解第n项斐波那契数列的值，main函数中通过循环调用fun函数来打印出前n项斐波那契数列的值。

c语言递归求斐波那契数列运行超时

在C语言中，递归求解斐波那契数列可能会导致运行超时的问题，主要是因为每次递归都会创建一个新的函数栈帧，存储当前的状态信息。当n值较大时，递归会非常频繁地调用自身，形成大量的堆叠，消耗大量的内存资源。

例如，递归版的斐波那契函数可以这样写：

int fibonacci(int n) {
    if (n <= 1)
        return n;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

这个函数的时间复杂度是O(2^n)，随着n的增长呈指数级增长，对于较大的n值，计算时间将变得非常长，可能导致程序崩溃或运行过慢。

为了避免这种问题，可以使用迭代或记忆化搜索（如动态规划）的方法来优化。迭代版本的斐波那契数列函数如下：

int fibonacci(int n) {
    int a = 0, b = 1, temp;
    if (n == 0) return a;
    for (int i = 2; i <= n; i++) {
        temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

这种方法的时间复杂度是线性的O(n)，效率大大提高。