0

这不是一个家庭作业问题。我只是想了解我自己的造就过程。作为一名计算机科学专业的学生，​​我参加了几场讨论递归概念的讲座。但是，在我看来，讲师对于堆栈帧的概念以及如何遍历调用堆栈以计算最终值有些模糊。我目前设想该过程的方式类似于从上到下构建一棵树（将项目推入调用堆栈 - 后进先出数据结构），然后爬上新构建的树，在此获得最终值到达顶部。也许是典型的例子：

def fact(n):
    if n == 0: 
        ans = 1
    else:
        ans = n * fact(n-1)
    return ans

value = fact(5)
print (value)

如上所述，我认为调用堆栈最终类似于以下（粗略）绘制的图：

+----------+
|    5      |
|    4      | 
|    3      |
|    2      |
|    1      |
 +----------+

每个数字都将被“封闭”在堆栈帧中，并且控制现在从底部（值为 1）到 2，然后是 3，依此类推。不过，我不完全确定操作员在过程中的位置。我会错误地假设在某些时候涉及抽象语法树（AST），还是存在包含运算符的第二个堆栈？

谢谢您的帮助。

~凯特琳

编辑：删除了“递归”标签并添加了“功能”和“堆栈帧”标签。

4

2 回答 2

1

这个问题更多的是关于函数调用如何工作，而不是关于递归。当一个函数被调用时，一个框架被创建并压入堆栈。框架包含一个指向调用代码的指针，以便程序知道函数调用后返回到哪里。运算符驻留在调用点之后的可执行代码中。

于 2014-03-15T08:21:44.330 回答
1

调用堆栈帧存储参数、返回地址和局部变量。代码（不仅是操作员）本身存储在其他地方。相同的代码在不同的堆栈帧上执行。

您可以在此处找到更多信息和可视化：http: //www.programmerinterview.com/index.php/recursion/explanation-of-recursion/

于 2014-03-15T08:16:12.957 回答