如何将生成斐波那契数列的C语言for循环转换为递归实现？

首先明确原代码的核心逻辑：从n=2到LIMIT=10，依次计算第n项斐波那契数（定义F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)），并输出当前项序号、数值，以及当前项与前一项的比值。

要转成递归实现，我们可以用尾递归的方式模拟循环的迭代过程——递归时传递当前的序号n，以及前两项的数值（对应原代码里的fn1和fn2），既避免重复计算，又保持和原代码一致的逻辑。

递归实现代码 #

// FibonacciNumbers_recursive
#include <stdio.h>
#define LIMIT 10

void recursiveFibonacci(int n, long fn1, long fn2);

int main() {
    showFibonacciValues();
    return 0;
}

void showFibonacciValues() {
    // 初始化递归起始条件：n从2开始，fn1是F(1)=1，fn2是F(0)=0
    recursiveFibonacci(2, 1, 0);
}

void recursiveFibonacci(int n, long fn1, long fn2) {
    // 递归终止条件：当n超过LIMIT时停止
    if (n > LIMIT) {
        return;
    }
    
    long fn = fn1 + fn2;
    double q = (double)fn / fn1;
    
    // 和原代码一致的输出格式
    printf("%7d%19ld%29.16f\n", n, fn, q);
    
    // 递归调用：下一次的n+1，fn1变为当前fn，fn2变为当前fn1
    recursiveFibonacci(n + 1, fn, fn1);
}

关键逻辑说明 #

• 递归起始条件：在showFibonacciValues中调用recursiveFibonacci(2, 1, 0)，对应原循环的初始状态——n从2开始，fn1是F(1)=1，fn2是F(0)=0。
• 递归终止条件：当n > LIMIT时直接返回，对应原循环中n <= LIMIT的循环边界。
• 迭代逻辑映射：每次递归计算当前项fn、比值q后，将下一次递归的参数更新为n+1、当前fn、当前fn1，完全对应原循环中fn2 = fn1; fn1 = fn; ++n的更新逻辑。

为什么不直接递归计算F(n)？ #

如果用long fib(int n) { return n <=1 ? n : fib(n-1)+fib(n-2); }这种直接递归写法，会产生大量重复计算（比如计算F(5)时会重复计算F(3)、F(2)多次），即使LIMIT=10影响不大，但效率远低于原循环和我们实现的尾递归版本。而我们的尾递归实现和原循环效率一致，每一步仅计算一次，无重复运算。

内容的提问来源于stack exchange，提问作者black Kiwi