在LispWorks中进行编程16：有关递归的更多信息

Category:UI界面编写 Tags : 在LispWorks中进行编程

有关递归的更多信息

通过编写递归函数（即引用自身的函数），可以最优雅，最轻松地解决许多问题。举个例子，这是一个在没有递归的情况下很难解决的问题，但使用递归很简单。

树上的递归

我们有一个简单的文字游戏，其中一个玩家命名一个字母，然后玩家轮流在任一端添加一个字母以创建一个新单词。第一个无法说话的球员输了。

我们可以将每个阶段的可能选择表示为树（这里我们在每个阶段只给出两个选择）：

在Lisp中，我们可以将此树表示为列表：

(word left-branch right-branch)

当一个分支是空的时我们把  nil，所以上面显示的树是：

(“n” (“in” (“pin” (“spin” nil nil) (“pint” nil nil)) (“ink” (“sink” nil nil) (“inky” nil nil))) (“on” (“son” (“sons” nil nil) (“song” nil nil)) (“one” (“gone” nil nil) (“ones” nil nil))))

如果我们在几行上列出列表，并且缩进，树结构会变得更清晰：

(“n” (“in”  (“pin”   (“spin” nil nil)   (“pint” nil nil))  (“ink”   (“sink” nil nil)   (“inky” nil nil))) (“on”  (“son”   (“sons” nil nil)   (“song” nil nil))  (“one”   (“gone” nil nil)   (“ones” nil nil))))

现在假设我们要编写一个过程打印树，它接受一棵树，就像上面那样，并打印树上的每个单词。在看到递归解决方案之前，问题有点棘手; 用语言：

要打印树：

• 在树的顶部打印单词
• 打印左侧分支
• 打印正确的分支

这是Lisp中的定义：

(defun print-tree (tree)  (if (null tree) nil    (progn      (print (first tree))      (print-tree (second tree))      (print-tree (third tree)))))

请记住（第一棵树）是树顶部的单词，（第二棵树）是左侧分支，（第三棵树）是右侧分支。我们使用  print-tree  本身来打印左分支和右分支。

我们运行如下：

CL-USER 1 > (defparameter tree ‘(“n” (“in” (“pin” (“spin” nil nil) (“pint” nil nil))(“ink” (“sink” nil nil) (“inky” nil nil))) (“on” (“son” (“sons” nil nil)(“song” nil nil)) (“one” (“gone” nil nil) (“ones” nil nil)))))CL-USER 2 > (print-tree tree) ninpinspinpintinksinkinkyonsonsonssongonegoneonesNIL

用数字递归

这是使用递归来解决数值问题的第二个例子。

n的阶乘定义为从1到n的所有数的乘积：1 * 2 * 3 * …. * n

您可以将此表达为递归定义，如下所示：

• 要找到阶乘n，找到阶乘（n-1）并乘以n。

我们还需要一条信息来阻止递归：

• 阶乘1是1。

现在我们可以编写阶乘的递归定义：

(defun factorial (n)  (if (= n 1) 1    (* n (factorial (- n 1)))))

检查它是否有效：

CL-USER 1 > (factorial 10)3628800

演习

1.计算树上的项目

编写一个过程计数树，用于计算树上项目的数量。使用上面定义的树，检查：

(count-tree tree)

给15。

2.在树上找到一个项目

修改print-tree以创建一个过程find-tree，用于检查单词是否在树上。

 

使用上面定义的树，检查：

(find-tree tree “gone”)

给出T，和：

(find-tree tree “tins”)

给出NIL。

3.找到第n个斐波纳契数

斐波那契序列是：

1 1 2 3 5 8 13 21 34

其中前两个术语是1，后面的每个术语是前两个术语的总和。

写一个 返回第n个斐波纳契数的递归函数  fib。

检查：

(fib 10)

给出55。

4.在Pascal的三角形上找到指定的数字

帕斯卡的三角形开始：

1      1   1    1   2   1  1   3   3   11   4   6   4   1

其中每个数字是它上面两个数字的总和。编写一个在第r行中给出第n个数字的函数。例如：

(pascal 3 5)

应该给6。

http://mip.i3geek.com