这个递归函数如何在C ++中运行？ [英] How Does This Recursive Function Operate in C++?

问题描述

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

  void递归（int x）
 {
 if（x <4）{
 cout < x<< ; //第一个输出：1 2 3 
递归（x + 1）; 
} 
 
 cout<< x<< ; //第二个输出：4 3 2 1 
} 
 
 int main（）
 {
递归（1）; 
} 
  

解决方案

C ++标准没有说明（IIRC是由实现来找到一个解决方案）。但在实践中，答案是堆栈。

在计算机科学中，堆栈是最后进先出的数据结构。按顺序1，2然后3进入堆栈，然后做三个弹出，你得到3，2然后1。

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

<然而，在IIRC的Algol编程语言的创新之一是支持递归。在同一时间，处理器堆栈变成了一个东西。

处理器堆栈（除了别的以外）允许你使用不同的方法来处理参数，局部变量和返回地址。您不需要为每个函数永久分配块 - 您在调用该函数时分配一个块（在堆栈的顶部）。当前堆栈帧的位置相对于当前的堆栈指针。这意味着你可以同时在堆栈上为同一个函数使用多个堆栈框架。

所以调用函数涉及在堆栈顶部创建一个新的堆栈框架堆栈和调整堆栈指针以适应。并且从函数返回涉及丢弃该堆栈帧并且将堆栈指针调回来，因此顶层堆栈帧现在是调用者的堆栈帧。调用者可能或可能不是相同的函数 - 没关系，因为每个调用都有自己的堆栈框架存储一组单独的参数，局部变量，单独的返回地址等。

因此，在 Recursion（3）调用之前，堆栈看起来像...

  | ------------------- + ----------------- -  + 
 |递归帧1 |递归帧2 | 
 | --------------- + --- + --------------- + --- + 
 | ??? | X | ??? | X | 
 | --------------- + --- + --------------- + --- + 
 | ??? | 1 | ??? | 2 | 
 | --------------- + --- + --------------- + --- + 
 ^ 
 | 
 STACK 
 POINTER 
  

？表示家务的东西，如返回地址。

I'd like to know how the 2nd output in the following code example is produced. How is the function able to count backwards after the if statement and recursive function call have ended?

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);
}

解决方案

I'm going to interpret the question as "how can the function remember what it was doing when it returns?".

The C++ standard doesn't say (IIRC it's left to implementations to find a solution that works). In practice, though, the answer is "the stack".

In computer science generally, a stack is a last-in-first-out data structure. Push the sequence 1, 2 then 3 into a stack then do three pops and you get 3, 2 then 1.

In the early days, programming languages often didn't support recursive or re-entrant calls. Each function/procedure had a little block of memory it owned where it stored its parameters, local variables and which function to return to after completion. If you tried to call a function that was already running, that would mean storing two sets of local variables and two return addresses in the space for one, so that was an error.

However, one of the innovations in IIRC the Algol programming language was support for recursion. And at around the same time, "processor stacks" were becoming a thing.

A processor stack (among other things) allows you to use a different method for handling parameters, local variables and return addresses. You don't need a permanently allocated block for each function - you allocate a block (at the top of the stack) when you call the function. The location of the current "stack frame" is relative to the current "stack pointer". And this means you can have multiple stack frames for the same function on the stack at the same time.

So calling a function involves creating a new stack frame at the top of the stack, and adjusting the stack pointer to suit. And returning from a function involves discarding that stack frame and adjusting the stack pointer back, so the top stack frame is now the stack frame for the caller. That caller may or may not have been the same function - it doesn't matter because each call got it's own stack frame storing a separate set of parameters, local variables, a separate return address etc.

So just before the Recursion (3) call, the stack would look something like...

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

The ??? represents "housekeeping" stuff like the return address.

这篇关于这个递归函数如何在C ++中运行？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！