Lisp 入门/第八章 递归函数

第八章 递归函数

一个小递归函数

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

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

a_n=a_n-1+d

我们有一个最简单的数列

0 2 4 6 8 10 ...

怎么表示呢，应该这样

a_n=a_n-1+2，其中a₁=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))

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