在lisp中递归是否有限制？

Question

我喜欢随时使用递归，这似乎是一种更自然的方式来循环实际循环。我想知道在lisp中递归是否有任何限制？就像在python中那样，在1000次循环后它会变得怪异吗？你可以用它来说游戏循环吗？

现在测试一下，简单计算递归函数。现在> 7000000！

非常感谢

Answer 1

首先，您应该了解尾调用的内容。

尾调用是不消耗堆栈的调用。现在您需要识别何时消耗堆栈。

我们来看一个阶乘的例子：

(defun factorial (n)
    (if (= n 1)
        1
        (* n (factorial (- n 1)))))

这是阶乘的非尾递归实现。为什么？这是因为除了从阶乘返回之外，还有一个待定计算。

(* n ..)

因此，每次调用阶乘时，您都会堆叠n。现在让我们编写尾递归因子：

(defun factorial-opt (n &key (result 1))
    (if (= n 1)
        result
        (factorial-opt (- n 1) :result (* result n))))

这里，结果作为参数传递给函数。所以你也在使用堆栈，但区别在于堆栈大小保持不变。因此，编译器可以通过仅使用寄存器并将堆栈留空来优化它。

然后factorial-opt更快，但可读性更低。 factorial仅限于堆叠的大小factorial-opt不是。所以你应该学习识别尾递归函数，以便知道递归是否有限。

可能有一些编译器技术将非尾递归函数转换为尾递归函数。也许有人可以在这里指出一些链接。

Answer 2

Scheme要求尾部调用优化，并且一些CL实现也提供它。但是，CL并没有强制要求它。

请注意，要使尾调用优化起作用，您需要确保不必返回。例如。 Fibonacci的一个简单的实现，其中需要返回并添加到另一个递归调用，不会进行尾调用优化，因此您将耗尽堆栈空间。