Hal*_*aby 2 compiler-construction recursion stack language-design language-implementation
函数调用通过堆栈数据结构处理.这足以支持递归吗？
完全拥有堆栈是编译器在支持递归时必须具有的特殊处理.
在早期版本的FORTRAN等较旧的编程语言中,运行时环境没有函数堆栈,每个函数在内存中的某个地方只有一个激活记录.这意味着递归根本不可能,因为如果你递归地调用一个函数,你将覆盖它唯一的激活记录,忘记你到达那里的上下文.
函数堆栈的引入首先使得递归实际上以编程语言表达.在此之前,程序员将使用递归作为抽象解决问题的工具,但由于缺少调用堆栈,因此必须将该代码转换为迭代逻辑.
为了使编程语言支持递归,它需要有一些动态维护调用堆栈的机制.这不必通过显式堆栈; 理论上,您可以动态分配所有堆栈帧并将它们链接在一起作为链接列表.这可能很有用,例如,如果您想支持协同程序或闭包,并且实际上需要在函数返回后保留旧的激活记录,以便以后可以存储数据.
希望这可以帮助!