一例scheme中的Recursion消除
ee.zsy
posted @ 2011年4月17日 01:53
in 未分类
, 1272 阅读
不知道是不是对Scheme中的语言特性有仇，这里再来消灭一样东西
——函数的递归定义。
定义会给函数定义一个名字，然后可以在这个还是中代码中用自己的名字递归的调用的自己。
那么现在的问题是匿名函数是否也能够递归的调用自己呢？
例子是这样的：
(define (sum x)
(if (zero? x)
0
(+ x (sum (- x 1)))))
用lambda写出来：
(define sum
(lambda (x)
(if (zero? x)
0
(+ x (sum (- x 1))))))
然后添加一个没有意义的参数：
(define (sum0 s)
(lambda (x)
(if (zero? x)
0
(+ x ((sum0 s) (- x 1))))))
柯里化（Currying），接受多个参数的函数可转化为接受一个参数并返回接受剩余参数函数的函数：
(define sum0
(lambda (s)
(lambda (x)
(if (zero? x)
0
(+ x ((sum0 s) (- x 1)))))))
它也等价于：
(define sum0
(lambda (s x)
(if (zero? x)
0
(+ x (sum0 s (- x 1))))))
现在的参数s不起任何作用，不过我们定义：
(define (sum n)
(sum0 sum0 n))
在这个对sum0的调用中，s等于sum0，于是可以把sum0代入得到：
(define (sum n)
(let ((sum0
(lambda (s x)
(if (zero? x)
0
(+ x (sum0 s (- x 1)))))))
(sum0 sum0 n)))
这里的let是lambda的语法糖，已经没有递归出现了。
于是利用这个例子中s和sum0等价，写为合法的表达式就是：
(define (sum n)
(let ((sum0
(lambda (s x)
(if (zero? x)
0
(+ x (s s (- x 1)))))))
(sum0 sum0 n)))
消灭一些语法糖后，包括define和let，我们得到：
(define sum
(lambda (n)
((lambda (sum0)
(sum0 sum0 n))
(lambda (s x)
(if (zero? x)
0
(+ x (s s (- x 1))))))))
调用(sum 100) ;=> 5050 ，现在目的达到了。
完整的代码是：
((lambda (n)
((lambda (sum0)
(sum0 sum0 n))
(lambda (s x)
(if (zero? x)
0
(+ x (s s (- x 1)))))))
100) ;=>5050
这里可以看到没有使用递归定义也能写出递归函数。
这也印证了ML语言中为什么let和let rec是要区分的使用。
评论 (0)