Lisp 入门/第八章 递归函数

维基教科书,自由的教学读本

第八章 递归函数[编辑]

一个小递归函数[编辑]

大家还记得数学上的递归定义么?

我们所知的最简单的定义就是等差数列。

an=an-1+d

我们有一个最简单的数列

0 2 4 6 8 10 ...

怎么表示呢,应该这样

an=an-1+2,其中a1=0

那么其定义就是 (defun dseq (n) (+ (dseq (- n 1)) 2))。注意,不要立刻输进去,因为这是一个错误的式子,先看懂它再说。

它的错误在哪里呢?如果dseq函数要求(dseq 3),它就会先去求(dseq 2),然后会再去求(dseq 1),再是(dseq 0),再是(dseq -1),以至无穷。它的错误就在于它不会停止。

这样的话,我们需要用到条件句。

完整的定义如下:

>(defun dseq (x) (cond ((= x 1) 0) (t (+ (dseq (- x 1)) 2))))

DSEQ
>(dseq 1)

0
>(dseq 2)

2
>(dseq 4)

6
>(dseq 999)

1996

后面的验证也说明它是正确的。

trace函数[编辑]

下面一个函数len用来计算一个表x的长(即元素个数)度。

>(defun len (x) (cond ((null x) 0) (t (+ (len (cdr x)) 1))))

递归式是(len (cdr x)) ,终结条件是(null x)为真。

我们输入

>(len '(a b c d))

4

Trace函数用来跟踪函数调用的情况

>(trace len)
(LEN)
>(len '(a b c d))

看看吧,会有很形象的东西出现