为什么递归函数比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

理论上的答案是递归版本其实是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 中的函数调用相对便宜且因此递归版本执行得更快。

PS。虽然这个问题是有道理的，而且答案实际上是普遍适用的（例如，同样的方法对 Python 和 CLISP 等是有效的），但应该意识到选择正确的算法（例如，线性合并排序而不是二次冒泡排序）比实施的 "micro-optimizations" 重要得多。

Answer 2

嗯...确实很奇怪，因为 Emacs 的函数调用（以及递归）实现效率不高。

我刚刚评估了下面的代码：

(defun sm-gcdi (a b)
  (let ((x a) (y b) r)
    (while (not (zerop y))
      (setq r (mod x y) x y y r))
    x))
(defun sm-gcdr (a b)
  (if (zerop b)
      a
    (sm-gcdr b (mod a b))))

(defun sm-test-iterative ()
  (let ((start (float-time)))
    (dotimes (_ 100000)
      (sm-gcdi 14472334024676221 8944394323791464))
    (- (float-time) start)))

(defun sm-test-recursive ()
  (let ((start (float-time)))
    (dotimes (_ 100000)
      (sm-gcdr 14472334024676221 8944394323791464))
    (- (float-time) start)))

然后尝试了 M-: (sm-test-recursive) 和 M-: (sm-test-iterative)，果然迭代版本对我来说更快。然后我做了M-: (byte-compile 'sm-gcdi)和M-: (byte-compile 'sm-gcdr)再试，速度差距更大

所以你的测量让我感到惊讶：它们不符合我的期望，也不符合我的测试。

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

Why is the recursive function performing better than the iterative function in elisp?

recursion

lisp

elisp