这个递归函数是如何在C++中运行的？

Question

我想知道如何生成下面的代码示例中的第二个输出。函数如何在if语句和递归函数调用结束后向后计数？

void Recursion(int x) 
{ 
    if(x < 4) { 
     cout << x << " "; // 1st output: 1 2 3 
     Recursion(x + 1); 
    } 

    cout << x << " "; // 2nd output: 4 3 2 1 
} 

int main() 
{ 
    Recursion(1); 
} 

Answer 1

我打算把这个问题解释为“函数如何记住函数返回时它正在做什么？”。

C++标准没有说（IIRC它留给执行找到一个有效的解决方案）。但实际上，答案是“堆栈”。

在计算机科学中，堆栈是一种后进先出的数据结构。将序列1,2和3推入一个堆栈，然后执行三次弹出，然后获得3,2然后1.

在早期，编程语言通常不支持递归调用或重入调用。每个函数/过程都拥有一小块内存，它存储它的参数，局部变量和完成后要返回的函数。如果你试图调用一个已经运行的函数，那就意味着将两组局部变量和两个返回地址存储在一个空间中，这是一个错误。

但是，IIRC Algol编程语言的创新之一是支持递归。大约在同一时间，“处理器堆栈”正在成为一件事情。

处理器堆栈（除其他外）允许您使用不同的方法来处理参数，局部变量和返回地址。您不需要为每个函数分配一个永久分配的块 - 当您调用该函数时，您会分配一个块（位于堆栈的顶部）。当前“堆栈帧”的位置是相对于当前的“堆栈指针”。这意味着您可以同时为堆栈中的相同功能设置多个堆栈帧。

所以调用一个函数需要在堆栈的顶部创建一个新的堆栈帧，并调整堆栈指针以适应。并且从函数返回涉及丢弃该堆栈帧并调回堆栈指针，所以顶层堆栈帧现在成为调用者的堆栈帧。这个调用者可能会或可能不会有相同的功能 - 它并不重要，因为每个调用都有自己的堆栈帧存储一组单独的参数，局部变量，单独的返回地址等。

所以就在Recursion (3)之前调用，堆栈看起来是这样的......

|-------------------+-------------------+ 
| Recursion Frame 1 | Recursion Frame 2 | 
|---------------+---+---------------+---+ 
| ???   | X | ???   | X | 
|---------------+---+---------------+---+ 
| ???   | 1 | ???   | 2 | 
|---------------+---+---------------+---+ 
             ^
             | 
             STACK 
            POINTER 

的???代表“看家”的东西，如返回地址。

Answer 2

想想第一次调用递归。

该函数打印一个“1”，然后其他东西将会发生，然后再打印一个“1”。

所以输出将是1 ... 1

现在想来第二次调用递归，它要打印一个“2”，那么其他的东西将要发生，那么这是一个“2”再次打印。

所以它的输出是2 ... 2。

棒这两个在一起，你会得到1 2 ... 2 1

然后就是继续前进。

Answer 3

它是否帮助，如果你看看这个：

string RecursiveReturn(int x) 
{ 
    if(x >= 4) { 
     return to_string(x); 
    } 

    return to_string(x) + " " + RecursiveReturn(x+1) + " " + to_string(x); 
} 

int main() 
{ 
    cout << Recursion(1); 
} 

递归调用就像任何其他函数调用......其被评估，当它返回调用函数继续。

Answer 4

堆栈描述了当“第一输出”时，执行到标准输出，则“第二输出”被插入到栈（“功能堆”）。

当函数“recursion”返回到“main”函数时，发生堆栈的展开或弹出内容。如果你正确地观察，这就是它如何产生输出。

Answer 5

这里发生的是前向递归和后退递归。在调用递归之前使用计数器（因为长计数器递增）通常是前向递归，而使用计数器之后是递归递归。

只进：

void Recursion(int counter) { 
    if(counter < n) { 
    cout << counter << " "; 
    Recursion(counter + 1); 
    } 
} 

第一次印刷的计数器比调用递归，一遍又一遍......这导致1 2 ... N-1：

call : 1 
print: 1 
call : 1+1 
print: 2 
call : 2+1 
print: 3 
call : 3+1 
if(...) // not true 
return: 
return: 
return: 
return: 

落后只有：

void Recursion(int counter) { 
    if(counter < stop) { 
    Recursion(counter + 1); 
    cout << counter << " "; 
    } 
} 

第一次调用递归一遍又一遍，不是首席t为反...这导致N-1 ... 2 1：

call : 1 
call : 1+1 
call : 2+1 
call : 3+1 
if(...) // not true 
return: 
print: 3 
return: 
print: 2 
return: 
print: 1 
return: 

注意：使用if语句柜台里面消除了ñ打印，它停止n-1个。

这是遍历算法的基础，如tree-traversal，它被称为预定序和后序。

Answer 6

您应该尝试单步执行代码，使用铅笔和纸张（或虚拟便笺本）执行代码。让我们继续函数定义收盘：

void Recursion(int x) 
{ 
1 if(x < 4) { 
2  cout << x << " "; // 1st output: 1 2 3 
3  Recursion(x + 1); 
. } 
. 
4 cout << x << " "; // 2nd output: 4 3 2 1 
5 return; 
} 

现在，让我们称之为main：

call main 
    call Recursion(1) -> x := 1 
     (1) if (x < 4) -> true 
      (2) cout << x << " ";         // with x == 1 
      (3) call Recursion(x + 1) -> x := 2 
       (1) if (x < 4)   -> true 
        (2) cout << x << " ";       // with x == 2 
        (3) call Recursion(x + 1) -> x := 3 
         (1) if (x < 4)   -> true 
          (2) cout << x << " ";     // with x == 3 
          (3) call Recursion(x + 1) -> x := 4 
           (1) if (x < 4)   -> false 
           (4) cout << x << " ";    // with x == 4 
          (5) end Recursion   -> x:= 3 
         (4) cout << x << " ";      // with x == 3 
        (5) end Recursion   -> x:= 2 
       (4) cout << x << " ";        // with x == 2 
      (5) end Recursion   -> x:= 1 
     (4) cout << x << " ";          // with x == 1 
    (5) end Recursion   -> del x 
end main 

而现在，你可以检查什么是outputed：cout << x << " ";与值依次称为：1​​，2，3 ，4，3，2，1，产生"1 2 3 4 3 2 1 "。