recursion - 为什么递归函数比elisp中的迭代函数表现更好？

Question

作为对我的一门课的测试，我们的老师要求我们测试著名的欧几里得算法的递归和非递归方法:

迭代

(defun gcdi (a b)
  (let ((x a) (y b) r)
    (while (not (zerop y))
      (setq r (mod x y) x y y r))
     x))

递归

(defun gcdr (a b)
  (if (zerop b)
     a
     (gcdr b (mod a b))))

然后我运行了一个测试:

(defun test-iterative ()
(setq start (float-time))
   (loop for x from 1 to 100000
     do (gcdi 14472334024676221 8944394323791464)) ; Fibonacci Numbers close to 2^64 >:)
 (- (float-time) start))

(defun test-recursive ()
(setq start (float-time))
   (loop for x from 1 to 100000
     do (gcdr 14472334024676221 8944394323791464)) ; Fibonacci Numbers close to 2^64 >:)
 (- (float-time) start))

然后我运行计时器:

(test-recursive)

: 1.359128475189209

(test-iterative)

: 1.7059495449066162

所以我的问题是，为什么递归测试比迭代测试执行得更快？迭代几乎总是比递归好吗？ elisp 是异常(exception)吗？

Answer 1

理论上的答案是递归版本其实是tail 递归，因此应该编译为迭代。

然而，disassembling 这些函数揭示了真相:

byte code for gcdi:
  args: (a b)
0       varref    a
1       varref    b
2       constant  nil
3       varbind   r
4       varbind   y
5       varbind   x
6       varref    y
7:1     constant  0
8       eqlsign   
9       goto-if-not-nil 2
12      constant  mod
13      varref    x
14      varref    y
15      call      2
16      varset    r
17      varref    y
18      varset    x
19      varref    r
20      dup       
21      varset    y
22      goto      1
25:2    varref    x
26      unbind    3
27      return    

对比

byte code for gcdr:
  args: (a b)
0       varref    b
1       constant  0
2       eqlsign   
3       goto-if-nil 1
6       varref    a
7       return    
8:1     constant  gcdr
9       varref    b
10      constant  mod
11      varref    a
12      varref    b
13      call      2
14      call      2
15      return    

您可以看到 gcdr 的指令数几乎是 一半，但包含两个 call 指令，这意味着 ELisp 显然不会将尾递归调用转换为迭代。 然而，ELisp 中的函数调用相对便宜且 因此递归版本执行得更快。

附言。虽然这个问题是有道理的，而且答案实际上是普遍适用的(例如，同样的方法对 Python 和 CLISP 等是有效的)，但应该意识到选择正确的算法(例如，线性合并排序而不是二次冒泡) -sort) 比实现的“微优化”重要得多。