Skip to main content
 首页 » 编程设计

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

2024年10月25日16grandyang

这里是 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" ?

请您参考如下方法:

只是以你的例子为例。

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

假设我们达到终止条件,在这种情况下 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”。