在lisp中递归是否有限制？

Question

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

现在测试一下,简单计算递归函数.现在> 7000000!

非常感谢

Answer 1

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

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

Answer 2

首先,您应该了解尾调用的内容.

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

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

(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不会.所以你应该学习识别尾递归函数,以便知道递归是否有限.

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