这个递归函数让我很困惑，这是怎么回事？

Question

我正在玩递归并完成了这个简单的功能。我假设它会打印 9-0 到标准输出，但是，它打印 0-9。我根本不明白这是怎么发生的。

int main()
{
        rec(10);
        return 0;
}

int rec(int n){
        if(n > 0)
                printf("%d\n", rec(n -1));
        return n;
}

Answer 1

printf 行上的 rec 函数在 printf 本身之前进行计算。因此，rec 函数的最深实例首先被打印。

Answer 2

这样想吧。

rec(10)
rec(9)
rec(8)
rec(7)
rec(6)
rec(5)
rec(4)
rec(3)
rec(2)
rec(1)
rec(0)

开始放松

printf("%d\n", 0);
printf("%d\n", 1);
printf("%d\n", 2);
printf("%d\n", 3);
printf("%d\n", 4);
printf("%d\n", 5);
printf("%d\n", 6);
printf("%d\n", 7);
printf("%d\n", 8);
printf("%d\n", 9);

Answer 3

让我们像这样重写代码：

int rec(int n){
        if(n > 0)
        {
                int retval = rec(n -1);
                printf("%d\n", retval);
        }
        return n;
}

是否清楚为什么 0 先打印在 9 之前？

Answer 4

正如 Michael Burr 在评论中所说，如果您想查看发生了什么，请在启用调试符号的情况下进行编译，如下所示：

gcc -o test -g test.c

然后像这样使用 gdb 运行。

gdb test

然后，要开始操作，请

start

在主函数中的第一次调用时输入 Which Break 。键入

step

以转到代码中的下一行，从那时起，只需按 Enter 键即可继续重复最后一个命令。如果您愿意，请输入继续以停止单步执行。您将看到每个阶段的值和评估线，这将确认上述答案。

希望提供一些有用的信息。

Answer 5

因为您正在创建 9 个环境 9 > 8> 7> 6> 5> 4> 3> 2> 1> 0，现在这些环境的处理方式与 a(b(c(d(e(f(g()))))) 相同，从最深的环境到第一个。

请记住，当您执行此操作 printf("%d",n(m)); 时，您实际上并没有打印任何内容，而是在说“打印 n(m) 的结果”，然后当它尝试解析 n(m)，您正在调用另一个打印并再次说“解析 n(m-1)”。

现在，当您到达 n(0) 时，它将返回 0，并由最后一次调用 printf 打印，因此它会打印 0 然后 1 .. 9。

Answer 6

int main()
{
        rec(10);
        return 0;
}

int rec(int n){
        if(n > 0)
                printf("%d\n", rec(n -1));
        return n;
}

一般来说，考虑一段代码。我们说迭代和递归解决方案之间存在直接关系，因此任何解决方案都可以迭代地编写，反之亦然。然而，在某些情况下，递归地表达算法似乎更容易（例如河内塔）。在上面的代码的情况下，等效的将是 for 循环构造。

这可以作为函数实现，如下所示：

void _for(int i, int n)
{
    if( i >= n ) return; // TERMINAL<br />
    // some expression (ie. printf("%d\n",i);)<br />
    _for(i+1,n) // RECURSION<br />
}

注意，这可以使用函数指针进行扩展。