效率:递归与循环

Question

这只是我的好奇心,但更有效,递归还是循环呢？

给定两个函数(使用常见的lisp):

(defun factorial_recursion (x)
    (if (> x 0)
        (* x (factorial_recursion (decf x)))
        1))

和

(defun factorial_loop (x)
    (loop for i from 1 to x for result = 1 then
        (* result i) finally
        (return result)))

哪个更有效率？

Answer 1

我甚至不必阅读你的代码.

循环对于阶乘更有效.进行递归时,堆栈上最多需要x个函数调用.

出于性能原因,您几乎从不使用递归.您使用递归来使问题更简单.

Answer 2

亩.

说真的,现在没关系.不是这个尺寸的例子.它们都具有相同的复杂性.如果您的代码不够快,这可能是您最后看到的地方之一.

现在,如果您真的想知道哪个更快,请测量它们.在SBCL上,您可以循环调用每个函数并测量时间.既然你有两个简单的功能,time就足够了.如果您的程序更复杂,那么分析器会更有用.提示:如果您不需要用于测量的分析器,您可能不需要担心性能.

在我的机器上(SBCL 64位),我运行了你的功能并得到了这个:

CL-USER> (time (loop repeat 1000 do (factorial_recursion 1000)))
Evaluation took:
  0.540 seconds of real time
  0.536034 seconds of total run time (0.496031 user, 0.040003 system)
  [ Run times consist of 0.096 seconds GC time, and 0.441 seconds non-GC time. ]
  99.26% CPU
  1,006,632,438 processor cycles
  511,315,904 bytes consed

NIL
CL-USER> (time (loop repeat 1000 do (factorial_loop 1000)))
Evaluation took:
  0.485 seconds of real time
  0.488030 seconds of total run time (0.488030 user, 0.000000 system)
  [ Run times consist of 0.072 seconds GC time, and 0.417 seconds non-GC time. ]
  100.62% CPU
  902,043,247 processor cycles
  511,322,400 bytes consed

NIL

将函数放在(declaim (optimize speed))顶部的文件中后,递归时间降至504毫秒,循环时间降至475毫秒.

如果你真的想知道发生了什么,试试dissasemble你的功能,看看里面有什么.

同样,这看起来对我来说不是问题.就个人而言,我尝试使用Common Lisp作为脚本语言进行原型设计,然后分析和优化缓慢的部分.从500毫秒到475毫秒是没有.例如,在一些个人代码中,我通过简单地向数组中添加元素类型来获得几个数量级的加速(因此在我的情况下使数组存储小64倍).当然,理论上重用该数组(在使其变小之后)并且不会反复分配它会更快.但是简单地添加:element-type bit它就足以满足我的需求 - 更多的变化需要更多的时间来获得额外的好处.也许我很草率,但"快"和"慢"对我来说并不重要.我更喜欢'足够快'和'太慢'.在大多数情况下,你的两个函数都"足够快"(或者在某些情况下两者都"太慢"),因此它们之间没有真正的区别.

Answer 3

如果你可以编写递归函数,使得递归调用是最后完成的事情(并且函数因此是尾递归的)并且你使用的语言和编译器/解释器支持尾递归,那么递归函数可以(通常)优化为真正迭代的代码,并且与同一函数的迭代版本一样快.

Sam I Am是正确的,但迭代函数通常比它们的递归函数更快.如果递归函数与执行相同操作的迭代函数一样快,则必须依赖于优化器.

这样做的原因是函数调用比跳转要贵得多,而且你消耗了堆栈空间,这是一种(非常)有限的资源.

你给出的函数不是尾递归,因为你调用factorial_recursion然后乘以它x.尾递归版本的一个例子是

(defun factorial-recursion-assist (x cur)
    (if (> x 1)
        (factorial-recursion-assist (- x 1) (+ cur (* (- x 1) x)))
        cur))

(defun factorial-recursion (x)
    (factorial-recursion-assist x 1))

(print (factorial-recursion 4))