C语言递归执行疑问：printf在递归后为何按升序输出？

原代码与输出 #

以下是一段实现1到n打印的C语言递归代码：

#include <stdio.h>
#include <stdlib.h>

/* --- 函数原型 --- */
void upton(int n); /* 打印1到n的递归函数 */

main()
{
  upton(20); /* 在屏幕上打印1到20的数字 */
  
  system("PAUSE");
  return 0;                                     
}

void upton(int n)
{
  if(n<1) return;    /* 若n小于1则返回 */
  
  upton(n-1);        /* 传入n-1的递归调用 */
  printf("%d\n",n);  /* 在连续递归后执行打印 */
}

代码输出如下：

1
2
3
4
...

核心疑问 #

1. upton()函数递归过程中，printf()在递归调用之后，为何能在每一轮递归中被执行？原本以为程序会卡在递归中直到终止，无法理解该语句的执行时机。
2. 递归调用的是upton(n-1)，为何最终输出是按升序排列的？

理解假设与验证 #

假设内容 #

使用递归时，每次函数调用都会在栈中存储以下信息：

• 递归变量（n）的当前值。
• 函数被“暂停”的位置地址（本例中每次递归都在upton(n-1)行暂停）。
  当递归因n<1终止后，调用栈开始回溯，从最后存入栈的层级最先执行，每个栈层级中递归调用行之后的暂停代码也会依次执行。

验证代码与输出 #

修改代码验证上述假设：

main()
{
  upton(6); /* 在屏幕上打印1到6的数字 */

  system("PAUSE");
  return 0;
}

void upton(int n)
{
  static int test=1;
  static char letter='f';

  if(n<1) return;    /* 若n小于1则返回 */

  upton(n-1);        /* 传入n-1的递归调用 */

  /* 递归后的测试代码 */
  printf("\nn=%d\n", n);
  printf("Hello!\n");
  printf("Test= %d%c\n",test, letter);
  test++;
  letter--;
}

得到的输出为：

n=1
Hello!
Test= 1f

n=2
Hello!
Test= 2e

n=3
Hello!
Test= 3d

n=4
Hello!
Test= 4c

n=5
Hello!
Test= 5b

n=6
Hello!
Test= 6a

结论 #

你的理解完全正确。

递归的执行依赖调用栈机制：每次调用upton(n)时，程序会为当前函数创建一个栈帧，存储n的当前值以及当前执行到的位置（也就是upton(n-1)这一行之后的代码地址），然后暂停当前函数，去执行新的upton(n-1)调用。

当递归到n=0时，触发if(n<1) return，此时最内层的函数调用完成并返回，程序开始回溯调用栈：从最后调用的upton(1)开始，执行它暂停时未完成的代码（也就是upton(n-1)之后的printf等语句），执行完后返回上一层的upton(2)，再执行它的后续代码，以此类推直到upton(20)的后续代码执行完毕。

这就是为什么printf能被每一轮递归执行，且输出是升序的原因——回溯时是从最小的n开始依次处理到最大的n。

内容的提问来源于stack exchange，提问作者Rodrigo Duarte