已经有名字的函数需要递归时用名字即可,但是对于匿名的 lambda
函数来说,就需要别的方法。看了一个下午 The Y Combinator (Slight Return) - Mike’s World-O-Programming,也没搞清楚怎么回事,但是代码实现起来没什么难度:
;; 是的,需要开启词法作用区域 -*- lexical-binding: t; -*-
;; 定义一个普通的递归函数
(defun len (l)
"求表的长度."
(if l
(+ 1 (len (cdr l)))
0))
;; 测试
(len '(1 2 nil 4))
=> 4
;; 输入一个非递归函数,输出一个递归函数
(defun Y (f)
"The strict Y combinator"
((lambda (x) (funcall x x))
(lambda (x) (funcall f (lambda (&rest y) (apply (funcall x x) y))))))
;; 定义递归函数 len2,但 len2 不出现在函数定义中
(fset 'len2
(Y (lambda (f)
(lambda (l)
(if l
(+ 1 (funcall f (cdr l)))
0)))))
;; 测试
(len2 '(1 2 nil 4))
=> 4