递归调用函数的能力是处理器或编程语言/编译器固有的能力吗？也许，两者都需要元素来支持递归？
我一直认为递归调用函数的能力完全是在编程语言中实现的，以及它如何布置其运行时堆栈，以及何时何地返回。我的假设是否正确，或者处理器是否具有允许递归的特定逻辑？
6 回答
7
处理器只是跳转到代码告诉它的地方。递归绝对是一种语言功能。
它也是一个编译器功能，只要编译器必须实现该语言。但如果它没有，我们会认为它坏了。
最后，当然操作的负担由处理器承担：它必须将上下文和变量压入堆栈帧，跳转到例程的入口点，执行指令，返回......你知道，处理器所做的事情.
于 2009-12-10T23:27:09.013 回答
5
所有现代处理器都能够递归，因为它们具有基于堆栈的函数调用和返回指令。
早期的计算机经历了一段非常艰难的时期。例如，IBM 360 对代码进行了布局，以便函数的返回值和局部变量与代码并列。递归调用会破坏前一次调用的值。
于 2009-12-10T23:28:41.230 回答
3
语。
你甚至并不总是需要一个堆栈来递归。有关不需要堆栈的递归类型的示例，请参见尾递归。
于 2009-12-10T23:27:27.053 回答
1
正如 Carl Smotricz 所说，CPU 只是遵循指令流中出现的分支指令。我们倾向于将递归称为普通函数调用，其中被调用的函数恰好与当前正在执行的函数相同，从高层次上讲，它具有一些非常有趣的效果。
于 2009-12-10T23:29:47.417 回答
1
即使在具有堆栈寻址模式的现代处理器上，有时您仍然希望在堆上分配调用帧，就像在 OS/360 等系统上所做的那样。例如，在 Scheme 中，可以捕获延续（基本上是调用帧加上活动局部变量绑定的表示）并保留它。如果您在函数内的全局变量中捕获延续，然后从该函数返回，则无法清除活动调用帧。一旦不再有任何对它的引用，它就会在某个时候被垃圾收集器清理，但与此同时，如果调用帧是在堆栈上分配的，则需要将它复制到其他地方（堆）。这有点与尾调用优化相反，您可以证明您永远不需要为递归调用分配堆栈帧。
于 2009-12-11T01:35:21.630 回答
1
您不需要对堆栈和递归调用的显式硬件支持，但处理器确实需要某些功能。我认为以下内容在基于寄存器的机器上就足够了：
- 您可以将存储的值写入程序计数器，例如使用跳转指令。这是需要返回的。
- 您可以用完一个存储您自己的堆栈指针的寄存器。
- 中断不会把事情搞得一团糟（尽管也许你可以忍受在中断上下文中没有堆栈，即使他们这样做了）。
引导代码必须分配一个内存区域用作堆栈，然后离开。
我猜一些处理器不提供这个。大多数处理器都明确支持堆栈指针和链接指针，以及有助于标准调用约定的指令。但是您可以发明并实现自己的调用约定。
于 2009-12-11T01:54:57.270 回答