理解堆栈框架如何在递归函数中工作

Question

Python/CS新手，试图了解特定递归函数如何“在引擎盖下”工作，函数的堆栈框架如何运行，它们“持有”的值是什么

我知道这里有很多关于递归函数的文章/帖子，这里有它们如何工作的示例，但递归的概念和堆栈如何工作/它们在递归函数中的作用有点棘手，我找不到任何清晰简洁的解释。

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

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

其输出为:< code>olleh

我认为＜code＞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"

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

Answer 1

只是以你为榜样散步。

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

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

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