跳转到内容

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))

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