c - C语言中的递归流程以及如何打印输出

Question

我的打印值(value)如何？

我知道递归会一次又一次地调用自身。据我所知，该函数应该返回空，因为该函数在打印之前被调用。 printf 是如何工作的？

recur(int i)
{
  if(i<0)
    return 0;
  recur(--i);
  printf("%d",i);
  recur(--i);
}

main()
{
  recur(2);
}

The output of this program is 
-1
0
1
-1

有人可以解释一下它是如何工作的吗？

Answer 1

要了解发生了什么，您必须了解递归的工作原理。每个递归函数都需要一个测试条件来中断递归和递归调用。您有if (i < 0)作为您的测试条件，然后您有两个递归调用 printf他们之间。

那么这是如何工作的？

您可以考虑递归和结束，直到触发退出条件 - 然后在递归调用返回时展开。让我们看看这是如何工作的。

递归

当您从 recur(2) 开始时在main ，逻辑采取什么路径来结束退出条件？

如果您简化函数并专注于满足测试条件之前发生的情况，您会得到类似于以下内容的内容:

void recur (int i) {
    if (i < 0)
        return;
    recur (--i);
    /* comes after return */
}

让我们来看看吧。第一次通话时，i = 2所以--1 预减发生在i = 1 , recur (1)执行。下次调用i = 0 , recur (0)再次被调用。最后，i = -1 ，第一个 recur(-1)发生，所以if (i < 0)执行并 return被调用。

现在怎么办？ -- 放松...

看看上面的缩短函数。当你 return ，您将从上次调用 recur(--i) 返回因此控制现在传递给第一个 recur(-1) 之后的下一个命令(如上面的 /* comes after return */ 所示)那么完整函数中的下一个命令是什么？

    printf("%d\n", i);
    recur (--i);

i 的值是多少这第一次发生是什么时候？ (提示:-1)。

所以printf被调用，然后接下来会发生什么？你的第二个recur(--i) 。有i = -2 ，if (i < 0) return;被触发，您就可以退出第二个 recur(-2) -- 后面没有命令，函数调用现已完成。

控制现在展开到上一个调用中的 i现在是0 ，printf称为第二个 recur(--i)输入 i = -1只需点击 return再次，您又放松了一个级别，到达 i = 1从第一次回来recur(--i)调用，1是输出。

第二个recur(--i)递减 i = 0 之后进入调用位置现在您再次递归到第一个位置 i = -1再次触发return这导致控制传递到 printf最后-1打印。

您现在递归到第二个 recur(--i)与 i = -2触发return并完成函数调用和递归。

因此，如果您通过两次递归调用返回递归函数的控制，并每次查看 printf已达到您输出 -1, 0, 1, -1 .

仍然认为具有多个递归调用的递归函数是个好主意吗？

(如果您是阿司匹林推销员，则最好避免使用它们，除非它们是您唯一合理的选择)

解决此类问题的唯一方法是(1)与调试器交 friend 并单步执行代码，保留草稿纸，记录何时输入调用，或者(2)复制并粘贴该函数向下跟踪每个级别的递归调用状态的页面并逐步进行。

始终是一个很好的学习体验，但是如果有可用的过程解决方案，则逻辑会更加直接，并且您可以避免每次递归调用的函数调用开销。递归函数有其用武之地，并且它们为某些问题提供了非常优雅的解决方案。但是，当您在每次调用时为局部变量分配单独的函数堆栈和空间时，您必须注意递归会发生多少次 - 这可能会导致 StackOverflow。