Lisp 入门/第八章 递归函数
< 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))
看看吧，会有很形象的东西出现