首先是递归获得阶乘的例子
(define f (lambda (x) (cond ((= x 1) 1) (else (* x (f (- x 1)))))))
对应的lambda (f):
(lambda (f) (lambda (x) (cond ((= x 1) 1) (else (* x (f (- x 1)))))))
但是参数是f，即是一个函数，所以要使得这段代码能够运行，应该传入一个函数。（ps：基础lambda表达式相关知识）
1 ;factorial2 2 ((lambda (f) 3 (lambda (x) 4 (cond ((= x 1) 1) 5 (else (* x (f (- x 1))))))) 6 (lambda (x) 7 (cond ((= x 1) 1) 8 (else (* x (f (- x 1))))))2)
最后传入的参数是2
这段代码中，最外层的括号包含了一个函数调用 (lambda (x) ... ) 2)，其中 2 是函数调用的参数。这个函数调用的参数是一个整数 2，它会被传递给内部的匿名函数。
内部的 lambda 表达式定义了一个函数，它接受一个参数 x，根据 x 是否等于 1 来返回不同的结果。如果 x 等于 1，则返回 1；否则返回 x 乘以 (f (- x 1)) 的结果，其中 f 是递归调用的函数。
在这个 lambda 表达式之前，有另一个 (lambda (f) ...) 表达式。这个表达式定义了一个函数 f，它接受一个参数 x，并根据 x 是否等于 1 来返回不同的结果。如果 x 等于 1，则返回 1；否则返回 x 乘以 (f (- x 1)) 的结果。这里的 (f (- x 1)) 表示递归调用，也就是调用函数 f 并传入参数 x-1。
在 (lambda (f) ...) 表达式内部定义的函数 f 就是前面内部的 lambda 表达式中提到的那个递归调用的函数。这里使用了一个技巧，将函数 f 作为参数传递给自身。这样，当我们在函数中调用 f 时，实际上就是在调用自身。
最终，这段代码的结果是计算 2! 的值，即 2 乘以 1，等于 2。这里使用了递归实现阶乘函数，而且没有出现栈溢出的问题。
最开始代入的 lambda(x) 是第一行的 (lambda (f) ...) 中的 (lambda (x) ...) 表达式。因为整个表达式是一个函数应用，即 (f f)，其中 (lambda (f) ...) 是被应用的函数，而 (lambda (x) ...) 是该函数的参数。
即此时第5行中的 f 函数是6-8 行的lambda 函数.
当代入3的时候，第8 行的 f 就没有定义了，出现错误，所以只能运行1-2的数值。
要改变这一状况，可以更改6-8行
1 ;factorial3 2 ((lambda (f) 3 (lambda (x) 4 (cond ((= x 1) 1) 5 (else (* x (f (- x 1))))))) 6 ((lambda (f) 7 (lambda (x) 8 (cond ((= x 1) 1) 9 (else (* x (f (- x 1))))))) 10 (lambda (x) 11 (cond ((= x 1) 1) 12 (else (* x (f (- x 1))))))))
这个时候就可以计算3的阶乘了。
我们观察上述式子可以发现，程序会在x == 1时停止，x != 1时会继续运行。我们可以让程序在 x != 1时生成(lambda (f) ....)。
1 ((lambda (f) 2 (lambda (x) 3 (cond ((= x 1) 1) 4 (else (* x ((f f) (- x 1))))))) 5 (lambda (f) 6 (lambda (x) 7 (cond ((= x 1) 1) 8 (else (* x ((f f) (- x 1))))))))
第4行中的两个 f 都是一样的，都是5-8行的那个表达式只不过这样子就可以无限调用了。
现在我们分析这个表达式，我们试着传2进去，去掉多余的式子，保留else，并展开(f f)，得到
1 (* 2 (((lambda (f) 2 (lambda (x) 3 (cond ((= x 1) 1) 4 (else (* x ((f f) (- x 1))))))) 5 (lambda (f) 6 (lambda (x) 7 (cond ((= x 1) 1) 8 (else (* x ((f f) (- x 1)))))))) 1))
我们可以看到，当x != 1时先执行(f f)生成了(F F)，然后当x == 1时就不再执行(f f)，程序停止。
1 ((lambda (f) (f f)) 2 (lambda (f) 3 (lambda (x) 4 (cond ((= x 1) 1) 5 (else (* x ((f f) (- x 1))))))))
第一行其实就是一段完整的代码，只是缩进有问题。
2-5行就是传入的参数
然后我们把else中的(f f)抽取出来，作为参数传递进去。
1 ((lambda (f) (f f)) 2 (lambda (f) 3 ( 4 (lambda (factorial) 5 (lambda (x) 6 (cond ((= x 1) 1) 7 (else (* x (factorial (- x 1))))))) 8 (f f) 9 ) 10 ) 11 )
现在我们似乎只要把(lambda (factorial) ...)取出，作为参数传递进去，就能得到一个更加通用的不用函数名就能实现递归的方法了。
但是这个表达式是错的，因为最后一行的(f f)会在传递进factorial之前运行，由于(f f)里还有(f f)，最终递归无法停止。我们得让(f f)不能先于factorial运行。
我们可以把最后一行(f f)变成lambda表达式
1 ((lambda (f) (f f)) 2 (lambda (f) 3 ((lambda (factorial) 4 (lambda (x) 5 (cond ((= x 1) 1) 6 (else (* x (factorial (- x 1))))))) (lambda (x) ((f f) x)))))
现在我们可以把(lambda (factorial) ...)提取出来了。
1 (lambda (target) 2 ((lambda (f) (f f)) 3 (lambda (f) 4 (target 5 (lambda (x) ((f f) x))))))
1 (((lambda (target) 2 ((lambda (f) (f f)) 3 (lambda (f) 4 (target 5 (lambda (x) ((f f) x)))))) 6 (lambda (factorial) 7 (lambda (x) 8 (cond ((= x 1) 1) 9 (else (* x (factorial (- x 1)))))))) 6)
这就是Y组合子
;Y Combinator
(define Y
(lambda (target)
((lambda (f) (f f))
(lambda (f)
(target
(lambda (x) ((f f) x)))))))
我们现在可以用Y组合子实现其它的匿名调用递归函数
;累加 (Y (lambda (acc) (lambda (x) (cond ((= x 0) 0) (else (+ x (acc (- x 1)))))))) ;计算list的长度 (Y (lambda (length) (lambda (l) (cond ((null? l) 0) (else (+ 1 (length (cdr l))))))))