python - 了解栈帧在递归函数中的工作原理

Question

这里是 Python/CS 新手，试图了解特定递归函数是如何“在幕后”工作的，即函数的堆栈帧如何运行以及它们“持有”什么值。

我知道这里有很多关于递归函数的文章/发布，并且有说明它们如何工作的示例，但是递归的概念和堆栈的工作方式/它们在递归函数中的作用有点棘手，我没有找到任何清晰简洁的解释。

假设我们有以下递归函数来反转字符串中的字符:

text = "hello"
def reverse_string(text):
        if len(text) <= 1:
            return text
        return reverse_string(text[1:]) + text[0]

输出:olleh

我认为 reverse_string(text[1:]) 的框架按如下方式工作:

Global frame
text    "hello"
reverse_string  

reverse_string
text    "hello"

reverse_string
text    "ello"

reverse_string
text    "llo"

reverse_string
text    "lo"

reverse_string
text    "o"

Return
value   "o"

但是在返回值 "o" 并且满足终止基本条件之后会发生什么？ text[0] 在函数中如何工作最终到达 "olleh" ？

Answer 1

只是以你的例子为例。

一旦我们达到终止条件，剩余的帧将以相反的顺序弹出。

假设我们达到终止条件，在这种情况下 return text 是“hit”并且 text = "o" 被返回。然后在上一帧中我们有 reverse_string(text[1:]) + text[0] 但这只是 reverse_string("o") + "l"= "o"+ "l"= "ol"= reverse_string(text[1:])，其中 reverse_string(text[1:]) 是前一帧的调用(text 等于“llo”)。继续这个逻辑，reverse_string("lo") + "l"= "ol"+ "l"= "oll"。

我们继续这个想法，直到我们到达“顶部”框架，我们最终返回“olleh”。