这里是 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”。
关于python - 了解栈帧在递归函数中的工作原理,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30610229/