关于emacs:迭代

上一章：变量

迭代，亦称循环，示意一段反复运行的程序，其状态可在每次反复运行的过程中发生变化。

基于递归函数能够模仿迭代过程。例如以下程序

(defun princ\' (x)
  (princ x)
  (princ "\n"))

(defun current-line ()
  (buffer-substring (line-beginning-position) (line-end-position)))

(defun every-line ()
  (if (= (point) (point-max))
      (princ "")
    (progn 
      (princ\' (current-line))
      (forward-line 1)
      (every-line))))

(find-file "foo.md")
(every-line)

Elisp 解释器在上述程序最初一个表达式 (every-line) 求值时，会转而对 every-line 函数定义里的每个表达式进行求值，然而当 Elisp 解释器在函数 every-line 的定义里又遇到了表达式 (every-line)，导致它不得不再次对 every-line 的定义里的每个表达式进行求值。该过程周而复始，在每一次重复对 every-line 的定义进行求值时，princ\' 会一直输入以后文本行，而 forward-line 又一直将插入点挪动到下一行的结尾。于是，上述程序便解决了读取以后缓冲区内的每一行文本并输入于终端这个问题。

咱们活着，也是相似的递归吧。于是，有人说，太阳每天都是新的。还有人说，人不能两次踏进同一条河流。如同咱们有寿命一样，Elisp 对函数的递归深度也有限度。every-line 这个函数，最多只能令 Elisp 解释器重复对其求值 max-lisp-eval-depth 次。`

max-lisp-eval-depth 是 Elisp 解释器的全局变量，它定义了函数递归深度。应用

(princ\' max-lisp-eval-depth)

可查看它的值，在我的机器上，后果 800，这意味着上述的 every-line 函数只能令 Elisp 解释器重复对其求值 800 次。这也意味着，假使以后缓冲区内的文本行数超过 800 行时，every-line 函数的定义会令 Elisp 解释器因解体而终止工作。它的临终遗嘱是

Lisp nesting exceeds‘max-lisp-eval-depth’

实践上，假使 Elisp 解释器可能对相似 every-line 这种尾部递归模式的函数予以优化，便可让本人用无休止地陷入对 every-line 的定义进行求值的过程中。这种优化，叫作尾递归优化。

不过，Elisp 解释器没有尾递归优化的性能，所以它必须提供迭代语法。Elisp 编程时最罕用的迭代语法是 while 表达式，用法如下

(while 逻辑表达式
  一段程序 )

若逻辑表达式的求值后果为 t，Elisp 便会重复执行 while 表达式里的那段程序，否则，Elisp 解释器会将 nil 作为求值后果，完结对 while 表达式的求值。这意味着 while 表达式的求值后果要么是 nil，要么是 Elisp 解释器永无休止对其进行求值的过程。事实上，while 表达式的求值后果是什么，并不重要，重要的是它的外部如何表白程序运行状态的变动及程序的响应。

基于 while 语法，可将上述 every-line 函数从新定义为

(defun every-line ()
  (while (< (point) (point-max))
    (princ\' (current-line))
    (forward-line 1)))

当初，不再放心因以后缓冲区行数过多的状况了，除非内存不够用，而且 every-line 的定义也更为简洁了。一举两得，然而假使我不先用递归函数模仿一下迭代过程，就很难有此刻愉悦的情绪。

同理，上一章从新定义列表反转函数

(defun reverse-list (x)
  (let ((y '()))
    (defun reverse-list\' (x)
      (if (null x)
          y
        (progn
          (setq y (cons (car x) y))
          (reverse-list\' (cdr x)))))
    (reverse-list\' x)))

也能够改写为 while 版本：

(defun reverse-list (x)
  (let ((y '()))
    (while (not (null x))
      (setq y (cons (car x) y))
      (setq x (cdr x)))
    y))

其中，not 是 Elisp 的逻辑取反函数。须要留神的是，上述代码中，局部变量 y 呈现在函数定义的最初，它就是函数的求值后果。因为，y 也是 S 表达式，Elisp 可对其进行求值。假使上述函数定义里的最初一行没有 y，那么 while 表达式的求值后果 nil 便是函数的求值后果。

有了迭代，那么递归函数还有必要再应用吗？

有必要。

一些树形构造的创立和遍历，例如二叉树或多叉树，用递归函数，不仅天然，而且代码也十分简洁，再者通常也无需放心递归深度的限度。以高度均衡二叉树为例，默认值为 800 的 max-lisp-eval-depth 足够了，因为叶结点数量高达 $2^{800}$ 的高度均衡二叉树简直不可能具备现实意义。

最初记住一句话吧，迭代是线性的递归。