c++ - 递归概念的澄清

Question

如果我编写如下所示的代码，我对递归有疑问

inorder(p){
if(p!=NULL){
 inorder(p->link);  //step 1
 cout<<p->info<<" "; //step 2
 inorder(p->link);  //step 3
}
} 

这里，我的疑问是，当执行步骤 1 时，控制权返回到函数，然后再次执行步骤 1，控制权将再次返回到函数，直到 p 为 NULL，如果这是过程，则控制将如何进入步骤 2，即“cout”和步骤 3 ...

我无法在大脑中循环代码...

Answer 1

在第1步“控制回到同一个函数”之前，CPU做了一个重要的步骤:它在inorder的代码中标记了需要重新执行一次“第二级”的地方"的 inorder 返回(这是第 1 步之后的位置)。在那里，“第二层”再次标记返回位置，然后再去“第三层”、“第四层”等等。最终，第 N 级得到一个 NULL，所以它立即返回。然后第 N-1 层开始打印 info，然后第二次调用 inorder。现在返回位置不同了 - 它就在第 3 步之后。一旦 N 级完成，N-1 级也完成，返回到 N-2-nd 级，然后到 N-3-rd，依此类推，直到第一级退出。

这是一个示例树:

      A
    /   \
   B     C
       /   \
      D     E

中序遍历的过程是这样的:

inorder(A)            -- step 1, level 1
  inorder(B)          -- step 1, level 2
    inorder(NULL)     -- returns
    cout << B         -- step 2, level 2
    inorder(NULL)     -- returns
  return              -- level 2 returns 
  cout << A           -- step 2, level 1
  inorder(C)          -- step 3, level 2
    inorder(D)        -- step 1, level 3
      inorder(NULL)   -- returns
      cout << D       -- step 2, level 3
      inorder(NULL)   -- returns
    return            -- level 3 returns
    cout << C         -- step 2, level 2
    inorder(E)        -- step 1, level 3
      inorder(NULL)   -- returns
      cout << E       -- step 2, level 3
      inorder(NULL)   -- returns
    return            -- level 3 returns
  return              -- level 2 returns
return                -- level 1 returns