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

後面的驗證也說明它是正確的。

下面一個函數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))

看看吧，會有很形象的東西出現