相互递归(1)
版权申明：本文为博主窗户(Colin Cai)原创，欢迎转帖。如要转贴，必须注明原文网址
http://www.cnblogs.com/Colin-Cai/p/10787636.html
作者：窗户
QQ/微信：6679072
E-mail：6679072@qq.com相互递归就是多个函数互相定义，最常见的就是两个函数，比如f和g，f的定义中用到g，而g的定义中用到f。
相互递归一样有无限递归的可能，最简单的:
f:x->g(x)
g:x->f(x)
给个最简单的没有无限递归的例子，判断一个正整数是不是偶数或者是不是奇数，用C++来描述如下:
bool is_odd(unsigned x);
bool is_even(unsigned x)
{
if(x == 0u)
return true;
return is_odd(x-1u);
}
bool is_odd(unsigned x)
{
if(x == 0u)
return false;
return is_even(x-1u);
}以上效率虽然不高（甚至不优化的情况下，可能会崩栈），但是is_even和is_odd两个函数毕竟是相互定义的，也是相互递归的一个经典例子。
Scheme当然一样支持相互递归，r5rs中也是以上述奇偶来做例子。
(define (even? x)
(if (zero? x)
#t
(odd? (- x 1))
)
)
(define (odd? x)
(if (zero? x)
#f
(even? (- x 1))
)
)再给个稍微复杂的例子，Scheme里的append是个常用的函数，它可以传入一组列表，得到这组列表首尾拼接在一起的列表。比如：(append '(1 2 3) '(4 5 6) '(7 8 9))得到(1 2 3 4 5 6 7 8 9)。
每个人学习Scheme的过程，基本必然伴随着append函数的自我实现。
以下是其中一种实现(当然，append有好几种不同的实现思想)：
(define (append . lst)
(if (null? lst)
'()
((apply _append (cdr lst)) (car lst))
)
)
(define (_append . lst)
(cond
((null? lst) (lambda (x) x))
((null? (cdr lst))
(lambda (x)
(if (null? x)
(car lst)
(cons (car x) ((_append (car lst)) (cdr x)))
)
)
)
(else (_append (apply append lst)))
)
)当然，_append一般应该实现在append的内部，我这么写也是为了表示的清楚一点。这种写法是一种相对高级一点的写法，采用的算子方式，不断用闭包来传递信息，并使用了相互递归，append和_append两个函数互相定义。
当然，一开始就说了，相互递归完全可以不只是两个函数之间的关系，可以是多个函数之间的关系。
我这里给个例子，把正整数按照除以3得到的余数分为三类，把整除3的数称为type0，把除以3余1的数称为type1，把除以3余2的数称为type2。于是定义三个谓词函数type0? type1? type2?
以下为实现：
(define (type0? x)
(if (= x 0)
#t
(type2? (- x 1))
)
)
(define (type1? x)
(if (= x 0)
#f
(type0? (- x 1))
)
)
(define (type2? x)
(if (= x 0)
#f
(type1? (- x 1))
)
)我们可以看到，
type0?的定义中用到type2?
type1?的定义中用到type0?
type2?的定义中用到type1?
测试一下，
(for-each
(lambda (x) (display x)(newline))
(map
(lambda (x)
(cons
x
(map (lambda (f) (f x)) (list type0? type1? type2?))
)
)
(range 20)
)
)得到
(0 #t #f #f) (1 #f #t #f) (2 #f #f #t) (3 #t #f #f) (4 #f #t #f) (5 #f #f #t) (6 #t #f #f) (7 #f #t #f) (8 #f #f #t) (9 #t #f #f) (10 #f #t #f) (11 #f #f #t) (12 #t #f #f) (13 #f #t #f) (14 #f #f #t) (15 #t #f #f) (16 #f #t #f) (17 #f #f #t) (18 #t #f #f) (19 #f #t #f)