为什么递归函数比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是个例外吗？

Answer 1

理论上的答案是递归版本实际上是尾递归的,因此应该编译为迭代.

然而,拆解 功能揭示了真相:

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    

VS

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中的函数调用相对便宜,因此递归版本执行得更快.

PS.虽然这个问题很有意义,但答案实际上是普遍适用的(例如,相同的方法对Python和CLISP尤其有效),应该意识到选择正确的算法(例如,线性合并 - 排序而不是二次泡沫-sort)比实现的"微优化"重要得多.