13.2 递归计算单词数

你可以编写递归方式和使用 while 循环的函数来计算单词数。让我们看看如何实现。

首先,我们需要认识到 count-words-example 函数有三个任务:它设置适当的条件来进行计数;它计算区域内的单词数;并向用户发送一条消息,告诉有多少个单词。

如果我们写一个单一的递归函数来执行所有这些任务,我们将为每个递归调用都收到一条消息。如果区域包含13个单词,我们将接收到十三条消息,依次排列。我们不想要这样!相反,我们必须编写两个函数来完成工作,其中一个(递归函数)将在另一个内部使用。一个函数将设置条件并显示消息;另一个将返回单词数。

让我们从引起消息显示的函数开始。我们可以继续称之为 count-words-example

这是用户将调用的函数。它将是交互式的。实际上,它将类似于我们先前版本的这个函数,只是它将调用 recursive-count-words 来确定区域中有多少个单词。

我们可以基于先前的版本轻松构造这个函数的模板:

;; 递归版本;使用正则表达式搜索
(defun count-words-example (beginning end)
  "documentation…"
  (interactive-expression…)

;;; 1. 设置适当的条件。
  (explanatory message)
  (set-up functions

;;; 2. 计算单词数。
    recursive call

;;; 3. 向用户发送消息。
    message providing word count))

定义看起来很简单,只是要注意递归调用返回的计数如何传递给显示单词计数的消息。经过一点思考,我们可以利用 let 表达式来实现:我们可以在 let 表达式的 varlist 中将一个变量绑定到区域内的单词数,由递归调用返回;然后 cond 表达式可以使用绑定来向用户显示该值。

通常,人们将 let 表达式内的绑定视为函数的主要工作的某种次要部分。但在这种情况下,您可能认为函数的主要工作,即计算单词数,是在 let 表达式内完成的。

使用 let,函数定义如下:

(defun count-words-example (beginning end)
  "打印区域内的单词数。"
  (interactive "r")

;;; 1. 设置适当的条件。
  (message "正在计算区域内的单词数... ")
  (save-excursion
    (goto-char beginning)

;;; 2. 计算单词数。
    (let ((count (recursive-count-words end)))

;;; 3. 向用户发送消息。
      (cond ((zerop count)
             (message
              "该区域没有任何单词。"))
            ((= 1 count)
             (message
              "该区域有1个单词。"))
            (t
             (message
              "该区域有 %d 个单词。" count))))))

接下来,我们需要编写递归计数函数。

递归函数至少有三个部分:再次执行测试,下一步表达式和递归调用。

再次执行测试确定函数是否将再次调用。由于我们在区域中计算单词数并可以使用一个每个单词都向前移动指针的函数,再次执行测试可以检查点是否仍然在区域内。再次执行测试应该找到点的值,并确定点是在区域结束的值之前,与之相等还是之后。我们可以使用 point 函数来定位点。显然,必须将区域结束的值作为参数传递给递归计数函数。

此外,再次执行测试还应该测试搜索是否找到了单词。如果没有找到,函数不应再次调用自身。

下一步表达式更改一个值,以便当递归函数应该停止调用自身时,它停止。更准确地说,下一步表达式更改一个值,以便在正确的时间,再次执行测试停止递归函数再次调用自身。在这种情况下,下一步表达式可以是将点按单词向前移动的表达式。

递归函数的第三部分是递归调用。

还需要一个执行函数工作的部分,一个执行计数的重要部分!

但是,我们已经有了递归计数函数的大纲:

(defun recursive-count-words (region-end)
  "documentation…"
   do-again-test
   next-step-expression
   recursive call)

现在我们需要填充这些槽。让我们从最简单的情况开始:如果点在区域结束的位置或之后,那么区域中不能有任何单词,因此函数应返回零。同样,如果搜索失败,就没有单词可计数,因此函数应返回零。

另一方面,如果点在区域内且搜索成功,则函数应再次调用自身。

因此,再次执行测试应如下所示:

(and (< (point) region-end)
     (re-search-forward "\\w+\\W*" region-end t))

请注意,搜索表达式是再次执行测试的一部分——如果其搜索成功,则函数返回 t,如果失败,则返回 nil。(See count-words-example 中的空白字符错误, 了解 re-search-forward 的工作原理的解释。)

再次执行测试是 if 子句的真值测试。显然,如果再次执行测试成功,则 if 子句的 then-部分应该再次调用函数;但如果失败,则 else-部分应该返回零,因为要么点在区域外,要么搜索失败,因为找不到单词。

但在考虑递归调用之前,我们需要考虑下一步表达式。这是什么?有趣的是,它就是do-again-test的搜索部分。

除了为do-again-test返回tnil外,re-search-forward在成功搜索时会作为副作用移动点。这是改变点值的操作,使得递归函数停止调用自身,当点通过区域完成移动。因此,re-search-forward表达式就是next-step-expression。

概述来看,recursive-count-words函数的主体如下:

(if do-again-test-and-next-step-combined
    ;; then
    recursive-call-returning-count
  ;; else
  return-zero)

如何融入计数机制?

如果你不习惯编写递归函数,这样的问题可能会让人头疼。但应该以系统的方式来解决。

我们知道计数机制应该以某种方式与递归调用关联起来。确实,由于next-step-expression通过一个单词将点向前移动,并且由于每个单词都会进行递归调用,计数机制必须是一个表达式,该表达式将一个添加到由recursive-count-words调用返回的值。

考虑几种情况:

从草图中我们可以看到,if的else部分对于没有单词的情况返回零。这意味着if的then部分必须返回一个值,该值是通过递归调用的返回值添加一的结果。

表达式将如下所示,其中1+是一个将一个添加到其参数的函数。

(1+ (recursive-count-words region-end))

整个recursive-count-words函数将如下所示:

(defun recursive-count-words (region-end)
  "documentation…"

;;; 1. do-again-test
  (if (and (< (point) region-end)
           (re-search-forward "\\w+\\W*" region-end t))

;;; 2. then-part: the recursive call
      (1+ (recursive-count-words region-end))

;;; 3. else-part
    0))

让我们看看这是如何工作的:

如果区域中没有单词,则if表达式的else部分被求值,因此函数返回零。

如果区域中有一个单词,则点的值小于region-end的值,并且搜索成功。在这种情况下,if表达式的true-or-false-test为true,将求值if表达式的then部分。计数表达式将被求值。该表达式返回一个值(这将是整个函数返回的值),即加一到递归调用返回的值。

同时,next-step-expression导致点跳过区域中的第一个(在这种情况下是唯一的)单词。这意味着当(recursive-count-words region-end)第二次求值时,由于递归调用的结果,点的值将等于或大于region end的值。因此,这次,recursive-count-words将返回零。零将添加到一,原始的recursive-count-words的求值将返回一加零,即一,这是正确的数量。

显然,如果区域中有两个单词,则第一次调用recursive-count-words将返回一个添加到调用recursive-count-words的区域剩余单词的值,即它添加到一,产生两个,这是正确的数量。

同样地,如果区域中有三个单词,则第一次调用recursive-count-words将返回一个添加到调用recursive-count-words的区域剩余两个单词的值,依此类推。

具有完整文档的两个函数如下:

递归函数:

(defun recursive-count-words (region-end)
  "在点和REGION-END之间的单词数。"

;;; 1. do-again-test
  (if (and (< (point) region-end)
           (re-search-forward "\\w+\\W*" region-end t))

;;; 2. then-part: the recursive call
      (1+ (recursive-count-words region-end))

;;; 3. else-part
    0))

包装器:

;;; 递归版本
(defun count-words-example (beginning end)
  "打印区域中的单词数。"

单词被定义为至少一个单词构成字符,后面跟着至少一个不是单词构成字符的字符。缓冲区的语法表决定了这些字符是哪些。"
  (interactive "r")
  (message "正在计算区域中的单词数...")
  (save-excursion
    (goto-char beginning)
    (let ((count (recursive-count-words end)))
      (cond ((zerop count)
             (message
              "该区域没有任何单词。"))
            ((= 1 count)
             (message "该区域有1个单词。"))
            (t
             (message
              "该区域有%d个单词。" count))))))