很难理解 C 中递归的工作原理

Question

#include <stdio.h>\n#include <stdlib.h>\n\n/* --- Prototype of functions --- */\nvoid upton(int n); /* recursive function to print the numbers from 1 to n */\n\n/* ========================================================================= */\nmain()\n{\n  upton(20); /* prints numbers from 1 to 20 on the screen */\n  \n  system("PAUSE");\n  return 0;                                     \n}\n\nvoid upton(int n)\n{\n  if(n<1) return;    /* returns if n less than 1 */\n  \n  upton(n-1);        /* recursive call with n-1 */\n  printf("%d\\n",n);  /* will print after successive recursions */\n}\n

\n

上面的代码生成以下输出：

\n

#include <stdio.h>\n#include <stdlib.h>\n\n/* --- Prototype of functions --- */\nvoid upton(int n); /* recursive function to print the numbers from 1 to n */\n\n/* ========================================================================= */\nmain()\n{\n  upton(20); /* prints numbers from 1 to 20 on the screen */\n  \n  system("PAUSE");\n  return 0;                                     \n}\n\nvoid upton(int n)\n{\n  if(n<1) return;    /* returns if n less than 1 */\n  \n  upton(n-1);        /* recursive call with n-1 */\n  printf("%d\\n",n);  /* will print after successive recursions */\n}\n

\n

有人知道如何向我解释 printf() 如何在 upton() 函数递归的每次传递中执行？

\n

我一直理解程序会卡在递归内部，直到递归失效。而且，由于 printf() 在递归之后，我不明白它是如何执行的......而且，由于递归是“upton(n-1)”，结果如何以升序打印命令？

\n

---- 已编辑 ----

\n

@pm100 @Allan Vento @olliejones

\n

让我看看我是否理解正确：

\n

因此，当我使用递归时，每次执行时都会将以下信息存储在堆栈级别中：

\n

#1 \xe2\x86\x92 递归变量 (n) 的当前值。

\n

#2 \xe2\x86\x92 函数“暂停”位置的地址[在这种情况下，在递归的每次传递中，函数在“upton(n-1)”行中“暂停”]。

\n

当递归最终失效（n<1）时，调用它的函数 [void upton(int n)] 开始执行保存在堆栈上的所有内容（堆栈上保存的最后一层将最先执行） ），这样，在递归行下方“暂停”的所有内容也将在堆栈的每个级别执行。

\n

我的结论正确吗？

\n

我做了以下修改来检验这个假设：

\n

main()\n{\n  upton(6); /* prints numbers from 1 to 6 on the screen */\n\n  system("PAUSE");\n  return 0;\n}\n\nvoid upton(int n)\n{\n  static int test=1;\n  static char letter=\'f\';\n\n  if(n<1) return;    /* returns if n less than 1 */\n\n  upton(n-1);        /* recursive call with n-1 */\n\n  /* Tests after recursion */\n  printf("\\nn=%d\\n", n);\n  printf("Hello!\\n");\n  printf("Test= %d%c\\n",test, letter);\n  test++;\n  letter--;\n}\n

\n

获得的输出是这样的：

\n

n=1\nHello!\nTest= 1f\n\nn=2\nHello!\nTest= 2e\n\nn=3\nHello!\nTest= 3d\n\nn=4\nHello!\nTest= 4c\n\nn=5\nHello!\nTest= 5b\n\nn=6\nHello!\nTest= 6a\n

\n

Answer 1

printf()您在到达基本情况之前调用递归函数n = 0，然后返回到之前的堆栈帧并 printf(..., 1)执行。然后你返回到之前的堆栈帧并执行printf(..., 2)等等。

我建议您修改递归函数以打印之前和之后的内容：

void upton(int n) {
  if(n<1) return;
  printf("before: %d\n", n);
  upton(n-1);
  printf("after: %d\n", n);
}

你会得到这个输出：

void upton(int n) {
  if(n<1) return;
  printf("before: %d\n", n);
  upton(n-1);
  printf("after: %d\n", n);
}

递归算法通常会产生紧凑的代码，但 C 标准没有指定尾部调用优化。如果您的编译器没有进行这种优化，您的堆栈将受到输入参数值的限制，并且如果您的输入足够大，您的程序将在堆栈空间耗尽时崩溃。

Answer 2

upton 不断调用自己，直到 n < 1。让我们从 5 而不是 20 开始

 upton(5) calls
  upton(4) calls
     upton(3) calls
      upton(2) calls
        upton(1) calls
          upton(0) returns
        upton(1) prints  1
      upton(2) prints 2
    upton(3) prints 3
  upton(4) prints 4
 upton(5) prints 5