斐波那契数列递归写法

### 斐波那契数列的递归实现

斐波那契数列可以通过递归来实现，这是一种直观但效率较低的方式。以下是C语言中的一个典型例子：

#include <stdio.h>

// 定义递归函数来计算斐波那契数
int fibonacci_recursive(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
}

int main() {
    int n;
    printf("输入一个数字: ");
    scanf("%d", &n);
    printf("斐波那契数列第 %d 项是: %d\n", n, fibonacci_recursive(n));
    return 0;
}

这段代码展示了如何通过递归定义斐波那契数列[^2]。

另一种不同的递归实现方法如下所示，在这个版本中，程序将持续打印直到达到指定的最大值而不是特定索引位置上的数值:

#include <stdio.h>
long long num1 = 1, num2 = 0, sum = 0;

void fbnq(long long a) {
    sum = num1 + num2;
    if (sum < a) { // 如果当前斐波那契数小于给定上限，则继续执行
        num1 = num2;
        num2 = sum;
        printf("%lld ", sum); // 输出当前斐波那契数
        fbnq(a);             // 继续递归调用自身
    }
}

int main() {
    fbnq(10); // 设置斐波那契序列的最大限值为10
    return 0;
}

此段代码实现了基于条件判断停止的递归过程，并不断输出新产生的斐波那契数直至满足终止条件[^1]。

尽管上述两种方法都可以用来生成斐波那契数列，但是它们的时间复杂度较高，尤其是对于较大的`n`值时性能较差。这是因为每次调用都会重复计算相同的子问题多次，从而导致指数级增长的操作次数[^3]。

为了提高效率，可以考虑采用记忆化技术或其他优化策略来减少不必要的重复运算。