Programming in Emacs Lisp笔记（十一）循环和递归

循环和递归

Emacs Lisp有两种方式循环执行语句：使用while循环，或者使用递归。

while

while测试它的第一个参数的值，如果为false，解释器将不会执行语句的body部分。如果为true，解释器将执行语句的body部分，然后重新测试第一个参数的值，开始下一轮循环。

while语句模板如下：

(while true-or-false-test
  body...)

使用while循环

如果while语句的true-or-false返回为true则body部分被执行。

对while求值的返回值是true-or-false-test的值。有趣的是while循环执行时如果没有发生错误将返回nil或false，而不管循环执行了多少次。while语句执行成功也不会返回true。

while循环和list

通常使用while循环来测试一个list是否包含了元素。如果有循环就执行，如果没有了循环就结束。这是一项重要的技术，下面将举例说明。

最简单的测试list是否有元素的方法是执行这个list：如果没有元素，则会返回空list，()，它与nil或false同义。如果有元素则将 返回这些元素。因为Emacs Lisp把任何蜚nil值当作true，如果把有元素的list作为while的判断条件，将使循环执行。

例：

(setq empty-list ())

对empty-list求值将返回nil。

(setq animals '(gazelle giraffe lion tiger))

如果把animals作为while循环的条件，如：

(while animals
       ...

当while检查它的第一个参数时，变量animals被执行，它将返回一个list。由于这个list不为nil，while将把这个值当作true。

为了防止while进入无限循环，需要一些机制来逐渐的清空list。一个常用的方法就是将传递给while语句的list替换为原来的list的CDR。每次都使用cdr函数，这样list将变短，最后list将变为空的list。这时while循环结束。

例如，上面的绑定到animals变量可以用下面的语句设置为原始list的CDR。

(setq animals (cdr animals))

使用while和cdr函数的模板如下：

(while test-whether-list-is-empty
  body...
  set-list-to-cdr-of-list)

例：print-elements-of-list

(setq animals '(gazelle giraffe lion tiger))

(defun print-elements-of-list (list)
  "Print each element of LIST on a line of its own."
  (while list
    (print (car list))
    (setq list (cdr list))))

(print-elements-of-list animals)

执行上面的代码，回显区将显示：

giraffe

gazelle

lion

tiger
nil

在循环中使用自增计数器

模板：

set-count-to-initial-value
(while (< count desired-number)         ; true-or-false-test
  body...
  (setq count (1+ count)))              ; incrementer

自增计数的例子

计算三角型中星号的数量，参数为层数，比如四层的三角型：

               *
              * *
             * * *
            * * * *

函数定义如下：

(defun triangle (number-of-rows)    ; Version with
                                    ;   incrementing counter.
  "Add up the number of pebbles in a triangle.
The first row has one pebble, the second row two pebbles,
the third row three pebbles, and so on.
The argument is NUMBER-OF-ROWS."
  (let ((total 0)
        (row-number 1))
    (while (<= row-number number-of-rows)
      (setq total (+ total row-number))
      (setq row-number (1+ row-number)))
    total))

使用：

(triangle 4)

(triangle 7)

第一行的结果为10，第二行的结果为28。

在循环中使用自减计数器

模板：

(while (> counter 0)                    ; true-or-false-test
  body...
  (setq counter (1- counter)))          ; decrementer

自减计数的例子

仍以上面的三角型为例，计算1到任意层的星号总数。

函数定义的第一版：

;;; First subtractive version.
(defun triangle (number-of-rows)
  "Add up the number of pebbles in a triangle."
  (let ((total 0)
        (number-of-pebbles-in-row number-of-rows))
    (while (> number-of-pebbles-in-row 0)
      (setq total (+ total number-of-pebbles-in-row))
      (setq number-of-pebbles-in-row
            (1- number-of-pebbles-in-row)))
    total))

然而，我们并不需要number-of-pebbles-in-row。

当执行triangle函数时，符号number-of-rows将被绑定到初始的值上。这个数值可以在函数体内作为局部变量被修改，而不用担心会 影响函数外部的值。这是Lisp中一个非常重要的特性；这意味着变量number-of-rows可以用于任何使用了number-of-pebbles -in-row的地方。

函数第二版如下：

(defun triangle (number)                ; Second version.
  "Return sum of numbers 1 through NUMBER inclusive."
  (let ((total 0))
    (while (> number 0)
      (setq total (+ total number))
      (setq number (1- number)))
    total))

简单来说，正常情况下while循环包含三个部分：

1. 在循环执行正确的次数后，while循环的判断语句将返回false。
2. 被循环执行的语句，它将返回需要的值。
3. 修改true-or-false-test返回值的语句，以便循环在执行正确的次数后停止。

使用dolist和dotimes节约时间

dolist和dotimes都是为循环提供的宏。在某些情况下比直接使用while循环简单一些。

dolist与在while中循环取list的CDR的方法类似，它在每次循环中自动取CDR截短list，并将截短后的list的CAR绑定到它的第一个参数上。

dotimes循环可以指定循环的次数。

dolist宏

举例来说，如果你想将一个list倒序排列，可以用reverse函数，例如：

(setq animals '(gazelle giraffe lion tiger))

(reverse animals)

这里演示了如何使用while循环实现倒序：

(setq animals '(gazelle giraffe lion tiger))

(defun reverse-list-with-while (list)
  "Using while, reverse the order of LIST."
  (let (value)  ; make sure list starts empty
    (while list
      (setq value (cons (car list) value))
      (setq list (cdr list)))
    value))

(reverse-list-with-while animals)

也可以用dolist宏实现：

(setq animals '(gazelle giraffe lion tiger))

(defun reverse-list-with-dolist (list)
  "Using dolist, reverse the order of LIST."
  (let (value)  ; make sure list starts empty
    (dolist (element list value)
      (setq value (cons element value)))))

(reverse-list-with-dolist animals)

在这个例子中，使用已存的reverse函数当然是最好的。第一个使用while循环的例子里。while先检查list是否有元素；如果有，它将 list的第一个元素添加到另一个list（它的第一个元素是nil）的第一个位置。由于添加元素的顺序是反的，因此原来的list被倒序排列了。

在使用while循环的语句中，(setq list (cdr list))语句截短了list，因此while循环最后停止了。在循环体中用cons语句创建了一个新的list。

dolist语句与while语句类似，dolist宏自动完成了在while语句中所写的一些工作。

while循环与dolist实现的两个方法不同之处在于dolist自动截短了list。'CDRs down the list'。并且它自动将CAR截短了的list的CAR赋给dolist的第一个参数。

dotimes宏

dotimes宏与dolist类似，但它可以指定循环次数。

dotimes的第一个参数是每次循环的计数器，第二个参数是循环次数，第三个参数是返回值。

举例来说，下例将number绑定到从0开始的数字，但不包含3，然后构造出一个包含3个数字的list。

(let (value)      ; otherwise a value is a void variable
  (dotimes (number 3 value)
    (setq value (cons number value))))

=> (2 1 0)

dotimes的返回值是value。

下面是一个使用defun和dotimes实现的triangle函数：

(defun triangle-using-dotimes (number-of-rows)
  "Using dotimes, add up the number of pebbles in a triangle."
(let ((total 0))  ; otherwise a total is a void variable
  (dotimes (number number-of-rows total)
    (setq total (+ total (1+ number))))))

(triangle-using-dotimes 4)

递归

递归函数使用不同的参数来调用自身。尽管执行的代码是相同的，但它们不是在同一线程执行。（不是同一个实例）

递归的组成

一个递归函数通常包含下面三个部分：

1. 一个true-or-false-test决定是否再次调用函数，在这里被称为do-again-test。

2. 函数名称。当这个函数被调用时，一个新的函数实例产生了，并被分配任务。

3. 一个函数语句，它在每次执行时返回不同的值。这里称为next-step-expression。这样，传递到新的函数实例的参数前与传递给前一个函数实例的参数不同。这将使得在执行了正确有循环次数后，条件语句do-again-test的值为false。

使用递归函数的简单模式如下：

(defun name-of-recursive-function (argument-list)
  "documentation..."
  (if do-again-test
    body...
    (name-of-recursive-function
         next-step-expression)))

递归函数每次执行时将产生一个新的函数实例，参数告诉了实例要做什么。一个参数被绑定到next-step-expression。每个实例执行时都有一个不同的next-step-expression。

next-step-expression的值被用于do-again-text。

next-step-expression的返回值被传递给新的函数实例，由它来决定是否停止或继续。next-step-expression被设计为在不需要循环后它能使do-again-test返回false。

do-again-test有时被称为停止条件（stop condition），因为它将在测试值为false时停止循环。

在list上使用递归

下面的例子使用了递归打印list中的各个元素。

(setq animals '(gazelle giraffe lion tiger))

(defun print-elements-recursively (list)
  "Print each element of LIST on a line of its own.
Uses recursion."
  (if list                              ; do-again-test
      (progn
        (print (car list))              ; body
        (print-elements-recursively     ; recursive call
         (cdr list)))))                 ; next-step-expression

(print-elements-recursively animals)

用递归代替计数器

前面章节说过的triangle函数可以用递归修改为：

(defun triangle-recursively (number)
  "Return the sum of the numbers 1 through NUMBER inclusive.
Uses recursion."
  (if (= number 1)                    ; do-again-test
      1                               ; then-part
    (+ number                         ; else-part
       (triangle-recursively          ; recursive call
        (1- number)))))               ; next-step-expression

(triangle-recursively 7)

在递归中使用cond

前一节中的triangle-recursively使用了if。它也可以使用cond，cond是conditional的缩写。

尽管cond不像if那样使用得很普遍，但它还是比较常见的。

使用cond的模板如下：

(cond
 body...)

body部分是一连串的list。

更完整的模板如下：

(cond
 (first-true-or-false-test first-consequent)
 (second-true-or-false-test second-consequent)
 (third-true-or-false-test third-consequent)
  ...)

当解释器执行cond语句时，它先执行body区的第一个语句的第一个元素。

如果true-or-false-test返回nil，则那个list的其它部分将不会执行。程序转到list串中的下一个list。当一个 true-or-false-test的返回值不为nil，则那条语句的其它部分将会执行。如果list串包含多个list，则它们依次执行并返回最后一 个语句的值被返回。

如果没有一个true-or-false-test的返回值为true，则cond语句返回nil。

使用cond实现的triangle函数：

(defun triangle-using-cond (number)
  (cond ((<= number 0) 0)
        ((= number 1) 1)
        ((> number 1)
         (+ number (triangle-using-cond (1- number))))))

递归模式

下面是3个常用的递归模式。

every

在every模式的递归中，动作将在list的每个元素上执行。

基本模型如下：

• 如果list为空，则返回nil。
• 否则，在list的首元素（list的CAR）上执行动作。
  • 通过递归在list的其它部分（CDR）上执行相同的操作。
  • 这步是可选的使用cons将正在操作的元素和已经操作过的元素列表合并。

例如：

(defun square-each (numbers-list)
  "Square each of a NUMBERS LIST, recursively."
  (if (not numbers-list)                ; do-again-test
      nil
    (cons
     (* (car numbers-list) (car numbers-list))
     (square-each (cdr numbers-list))))) ; next-step-expression

(square-each '(1 2 3))
    => (1 4 9)

如果number-list为空，则什么也不做。如果它有内容，则通过递归构造一个list各个元素乘方值的list。

前面介绍过的print-elements-recursively函数，是另一个every模式的递归，不同的是这里使用了cons合并元素。

(setq animals '(gazelle giraffe lion tiger))

(defun print-elements-recursively (list)
  "Print each element of LIST on a line of its own.
Uses recursion."
  (if list                              ; do-again-test
      (progn
        (print (car list))              ; body
        (print-elements-recursively     ; recursive call
         (cdr list)))))                 ; next-step-expression

(print-elements-recursively animals)

print-elements-recursively函数的处理流程：

• 如果list为空，不执行操作。
• 如果list含有至少一个元素，
  • 在list的首元素（CAR）上执行操作。
  • 通过递归调用在其它的元素上执行操作。

accumulate

accumulate递归模式，在每个元素上都执行动作，动作的执行结果与对下一个元素执行操作的结果进行累积。

这与在every模式中使用cons类似，只是不是使用cons，而是使用其它的方式合并。

工作模式如下：

• 如果list为空，返回0或其它常量
• 否则，在list的CAR上执行动作
  • 使用+或其它操作合并当前操作的元素和已经操作过的元素
  • 递归方式在list的其它部分执行

例如：

(defun add-elements (numbers-list)
  "Add the elements of NUMBERS-LIST together."
  (if (not numbers-list)
      0
    (+ (car numbers-list) (add-elements (cdr numbers-list)))))

(add-elements '(1 2 3 4))
   => 10

keep

在keep递归模式中，list中的每个元素被测试，如果被操作的元素符合要求或者对元素的计算结果符合要求则保存该元素。

这与every模式也很类似，只是在这里如果元素不符合要求则被忽略。

这种模式的三个部分：

• 如果list为空，则返回nil
• 如果list的CAR符合要求
  • 在元素上执行操作，并使用cons合并它
  • 递归调用处理list中的其它元素
• 如果list的CAR不符合要求
  • 忽略这个元素
  • 递归调用处理list中的其它元素

例如：

(defun keep-three-letter-words (word-list)
  "Keep three letter words in WORD-LIST."
  (cond
   ;; First do-again-test: stop-condition
   ((not word-list) nil)

   ;; Second do-again-test: when to act
   ((eq 3 (length (symbol-name (car word-list))))
    ;; combine acted-on element with recursive call on shorter list
    (cons (car word-list) (keep-three-letter-words (cdr word-list))))

   ;; Third do-again-test: when to skip element;
   ;;   recursively call shorter list with next-step expression
   (t  (keep-three-letter-words (cdr word-list)))))

(keep-three-letter-words '(one two three four five six))
    => (one two six)

无延时的递归

这部分讲解了如何将递归函数拆分成多个函数部分（比如：初始化函数、辅助函数），减少递归函数body部分的判断，使得递归函数本身只需要处理好递归操作，提高了递归函数的执行速度。

评论

2 楼 Jamsa 2007-07-19  

准备在读完后再整理一下合成一篇，与大家分享！

1 楼 metaphy 2007-07-19  

整理一下哦
可以合成一篇......................方便下载 -_-#