好吧,这可能是一个愚蠢的问题。但我认为每当你返回一些东西时,堆栈中的项目就会被弹出。但在递归的情况下,堆栈中的项目会不断堆积,直到到达基本情况。然后它开始弹出。我想知道这是为什么。
还有,一个项目到底什么时候从堆栈中弹出?
我将假设“项目”,您指的是函数调用堆栈的堆栈框架,而不是堆栈数据结构中的项目元素(其操作类似于调用堆栈)。我希望能够消除有关调用堆栈如何工作的困惑。
另请注意,进程中的每个线程都有自己的调用堆栈。现在,假设我们正在使用一个具有一个正在运行的执行线程的进程。
递归函数是调用自身的函数。每当调用函数时,到达函数调用指令的线程都会创建一个堆栈帧。堆栈帧是一块内存,包含执行被调用函数所需的所有数据(变量、参数等)。该帧被“推”到调用堆栈的顶部。当前正在执行的调用函数被暂时挂起,堆栈指针向上移动到新的帧,然后执行。
如果没有基本情况或函数不再进行递归调用的条件状态,递归将无限期地进行下去。发生这种情况时,操作系统会在进程超出其堆栈使用量(通常约为 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,退出。
我建议阅读维基百科的文章,例如基于堆栈的内存分配和调用堆栈,并编写大量微型递归程序(如此处的示例)以了解它们是如何工作的。
例如:
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
。
这就是为什么我们可以递归。
也许我的解释很无聊,我想分享给你一个可视化链接,你很想看看。