論壇

递归定义指的是在定义中(直接或间接地)引用自身的定义. 乍看上去, 递归是一种很不合理的东西, 但实际上却很简单. 我们将用许多例子来刻画递归, 这些例子将反复出现.

第一个例子是阶乘, 它的定义是众所周知的.

我们可以将其直接地翻译为Scheme过程.

第二个例子是Fibonacci数列, 它的每一项, 可以通过简单的递归关系式确定.

同样地, 将其翻译为Scheme过程是轻而易举的.

第三个例子是最大公因数 (Euclid算法).

Euclid算法在终止时能够给出正确的结果, 仰赖于以下事实.

Euclid算法必然能够在有限步骤内终止, 是显然的, 因为根据余数的定义, 它小于除数b. 最粗略的估计告诉我们过程gcd最多进行b步, 一个更好的上界估计可以参看Lamé定理, 有趣的是, 它里面出现了Fibonacci数列.

第四个例子是一个互递归的例子. even?判断一个自然数是否是偶数, odd?判断一个自然数是否是奇数.