如何用C语言无静态/全局变量递归打印斐波那契数列

要求将现有打印斐波那契数列代码中的for循环替换为递归调用实现，不允许使用静态变量或全局变量，核心需求为：如何将for循环与现有函数整合，或是编写新的递归函数实现从0到用户输入值n的遍历运行？

初始待修改代码 #

// 编写C/C++程序用递归打印斐波那契数列
#include <stdio.h>

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

int main()
{
    int n;
    printf("输入要打印的元素个数: ");
    scanf("%d", &n);
    printf("斐波那契数列: ");
    for (int i = 0; i < n; i++)
    {
        printf("%d", fib(i));
    }
    return 0;
}

首次尝试实现（运行异常） #

编写递归函数替换for循环后，代码仅输出0，不符合预期：

// 编写C/C++程序用递归打印斐波那契数列
#include <stdio.h>

int fib(int n)
{
    if (n == 0 || n == 1)
        return n;
    else
        return fib(n - 1) + fib(n - 2);
}
void rec(int n)
{
    if(n>0)
        rec(n-1);
    else
        printf("%d", fib(n));
}

int main()
{
    int n;
    printf("输入要打印的元素个数: ");
    scanf("%d", &n);
    printf("斐波那契数列: ");
    // 注释掉原for循环
    // for (int i = 0; i < n; i++)
    // {
    //     printf("%d", fib(i))
    // }
    rec(n);
    return 0;
}

首次尝试失败原因 #

• 递归函数rec仅在n == 0分支执行打印操作，n > 0分支仅触发递归未添加打印逻辑，导致仅输出第一个元素0
• 调用rec函数时直接传入了n，而原for循环的遍历范围是0到n-1，调用参数需要调整为n-1才能输出对应数量的元素

不符合要求的实现方案（使用静态变量，被禁止） #

以下方案使用静态变量实现了递归打印，但不符合不允许使用静态/全局变量的要求：

void fib(int n)
{
    static int n1 = 0, n2 = 1, n3;
    if (n > 0)
    {
        n3 = n1 + n2;
        n1 = n2;
        n2 = n3;
        printf("%d ", n3);
        fib(n - 1);
    }
}
int main()
{
    int n;
    printf("输入要打印的元素个数: ");
    scanf("%d", &n);
    printf("斐波那契数列: ");
    printf("0 1 ");
    fib(n - 2);
    return 0;
}

最终正确实现代码 #

// 编写C程序用递归打印斐波那契数列
#include <stdio.h>

int fib(int n)
{
    if (n == 0 || n == 1)
        return n;
    else
        return fib(n - 1) + fib(n - 2);
}
void rec(int n)
{
    if (n >= 0)
    {
        rec(n - 1);
        printf("%d ", fib(n));
    }
}

int main()
{
    int n;
    printf("输入要打印的元素个数: ");
    scanf("%d", &n);
    printf("斐波那契数列: ");
    // 注释掉原for循环
    // for (int i = 0; i < n; i++)
    // {
    //     printf("%d ", fib(i));
    // }
    rec(n-1);
    return 0;
}

内容的提问来源于stack exchange，提问作者Shubham Garg