functional-programming - 尾递归和堆栈递归函数有什么区别？

Question

在纯函数式语言中，例如将阶乘函数写为，

fact.0 = 1
fact.n = n*fact.n-1

由于这个函数是堆栈递归的，任何人都可以解释堆栈递归和告诉递归函数之间的区别吗？

提前致谢。

Answer 1

尾递归和堆栈递归（如您所说）之间的区别在于，尾递归函数可以转换为不使用调用堆栈的命令式代码（即，本质上是一个 while 循环），而使用堆栈递归，堆栈深度是与递归深度成正比。这可能意味着程序溢出堆栈。

请注意，“转换为命令式代码”是代码生成中通常发生的事情，因为编译器的输出语言通常是汇编、C 或其他一些低级命令式语言。

请注意，这与函数式甚至纯函数式语言无关，在每种支持递归的语言中都有同样的问题。只是在某些函数式语言中，递归是唯一的循环方式。