为什么递归返回时堆栈中的项没有立即弹出？

Question

好吧，这可能是一个愚蠢的问题。但我认为每当你返回一些东西时，堆栈中的项目就会被弹出。但在递归的情况下，堆栈中的项目会不断堆积，直到到达基本情况。然后它开始弹出。我想知道这是为什么。

还有，一个项目到底什么时候从堆栈中弹出？

Answer 1

我将假设“项目”，您指的是函数调用堆栈的堆栈框架，而不是堆栈数据结构中的项目元素（其操作类似于调用堆栈）。我希望能够消除有关调用堆栈如何工作的困惑。

另请注意，进程中的每个线程都有自己的调用堆栈。现在，假设我们正在使用一个具有一个正在运行的执行线程的进程。

---

递归函数是调用自身的函数。每当调用函数时，到达函数调用指令的线程都会创建一个堆栈帧。堆栈帧是一块内存，包含执行被调用函数所需的所有数据（变量、参数等）。该帧被“推”到调用堆栈的顶部。当前正在执行的调用函数被暂时挂起，堆栈指针向上移动到新的帧，然后执行。

如果没有基本情况或函数不再进行递归调用的条件状态，递归将无限期地进行下去。发生这种情况时，操作系统会在进程超出其堆栈使用量（通常约为 1 MB）时发送信号来终止进程。

到达基本情况并执行函数中的最后一行代码后，线程开始从上到下解析堆栈帧，并在执行完成时将它们从堆栈中弹出（它们可能会执行更多工作或进行额外的递归调用） .

弹出相当于释放与帧相关的内存，处理返回值，将堆栈指针移回调用者并在调用处恢复执行。

这是一个用 C 和 Python 编写的示例程序，其中包含递归函数和图表：

#include <stdio.h>

void count_to(int n) {
    if (n > 0) {
        count_to(n - 1);
    }

    printf("%d\n", n);
}

int main() {
    count_to(4);
    return 0;
}

def count_to(n):
    if n > 0:
        count_to(n - 1)
    
    print(n)

count_to(4)

这是程序的输出：

0
1
2
3
4

这是执行期间调用堆栈的样子：

[count_to(4)]  <-- top of call stack/stack pointer
[main]         <-- bottom of call stack

[count_to(3)]  <-- 
[count_to(4)]  
[main]         

[count_to(2)]  <-- 
[count_to(3)]
[count_to(4)]
[main]         

[count_to(1)]  <--
[count_to(2)]
[count_to(3)]
[count_to(4)]
[main]         

[count_to(0)]  <--
[count_to(1)]
[count_to(2)]
[count_to(3)]
[count_to(4)]
[main]         

此时，还没有打印任何内容。该线程刚刚将函数调用添加到堆栈中。但是一旦我们调用

count_to(0)

，递归就会停止。当我们弹出堆栈帧时，每个函数都会打印其本地值

n

并返回给其调用者。

print(0)
return

[count_to(1)]  <-- 
[count_to(2)]
[count_to(3)]
[count_to(4)]
[main]         

print(1)
return

[count_to(2)]  <-- 
[count_to(3)]
[count_to(4)]
[main]         

print(2)
return

[count_to(3)]  <--
[count_to(4)]
[main]         

print(3)
return

[count_to(4)]  <--
[main]         

print(4)
return

[main]         <--

最后执行返回到main，退出。

---

我建议阅读维基百科的文章，例如基于堆栈的内存分配和调用堆栈，并编写大量微型递归程序（如此处的示例）以了解它们是如何工作的。

Answer 2

例如：

def bar(n):
    if n > 0:
        print(n)
        return bar(n-1)
    return 'end'

在

return bar(n-1)

语句中，我们首先执行

bar(n-1)

，然后返回

the return value

的

bar(n-1)

。

当我们执行

bar(n-1)

时，我们会遇到类似的情况，除非

n > 0

不再是

True

。

这就是为什么我们可以递归。

也许我的解释很无聊，我想分享给你一个可视化链接，你很想看看。