前段时间学习eopl时了解到了cps风格的写法，于是就随便找了个算法练习了下，结果有了一些意料之外的发现。
说起递归，最基础最经典的应该就算斐波那契数列了，两种最基本的写法是：
//递归写法
function fib(n) {
if (n <= 2) {
return 1;
} else {
return fib(n - 1) + fib(n - 2)
}
}
或
//循环写法
function fib(n) {
if (n <= 2) {
return 1;
}
let a = 1, b = 1;
for (var i = 2; i < n; i++) {
var temp = a;
a = b;
b = temp + b;
}
return b;
}
以及
//尾递归迭代写法
function fib(n) {
function iter(a, b, i) {
if (i == n) {
return b;
} else {
return iter(b, a + b, i + 1)
}
}
return iter(0, 1, 1)
}
第一种递归写法非尾递归，会导致栈溢出；第二种是用循环实现，下面暂不讨论；第三种则是第二种方式的一种尾递归写法。然后我们将第一段和第三段程序改为另一种样子。
各种语言的实现
javascript实现
function fib(n) {
return (function iter(n, f) {
return n == 1
? f(0, 1)
: iter(n - 1, (a, b) => f(b, a + b))
})(n, (n1, n0) => n0)
}
function fib(n) {
return (function rec(n, f) {
return n <= 2
? f(1)
: rec(n - 1, (a) => rec(n - 2, (b) => f(a + b)))
})(n, (a) => a)
}
kotlin实现
fun main(args: Array
println("fib1:" + fib1(30))
println("fib2:" + fib2(20))
}
fun fib1(n: Int): Int {
tailrec fun iter(n: Int, f: (Int, Int) -> Int): Int {
return when (n) {
1 -> f(0, 1)
else -> iter(n - 1) { a, b -> f(b, a + b) }
}
}
return iter(n) { n1, n0 -> n0 }
}
fun fib2(n: Int): Int {
tailrec fun rec(n: Int, f: (Int) -> Int): Int {
return when {
n <= 2 -> f(1)
else -> rec(n - 1) { a -> rec(n - 2) { b -> f(a + b) } }
}
}
return rec(n) { a -> a }
}
scala实现
import scala.annotation.tailrec
object Fib {
def main(args: Array[String]): Unit = {
println(s"fib1:${fib1(20)}")
println(s"fib1:${fib2(10)}")
}
def fib1(n: Int): Int = {
@tailrec
def iter(n: Int, f: (Int, Int) => Int): Int = n match {
case 1 => f(0, 1)
case _ => iter(n - 1, (a, b) => f(b, a + b))
}
iter(n, (n1, n0) => n0)
}
def fib2(n: Int): Int = {
def rec(n: Int, f: Int => Int): Int = {
if (n <= 2) f(1)
else rec(n - 1, a => rec(n - 2, b => f(a + b)))
}
rec(n, a => a);
}
}
Common Lisp 实现
(defun fib (n)
(labels ((iter (n f)
(if (= n 1)
(funcall f 0 1)
(iter (- n 1)
(lambda (a b)
(funcall f b (+ a b)))))))
(iter n (lambda (n1 n0) n0))))
(defun fib (n)
(labels ((rec (n f)
(if (<= n 2)
(funcall f 1)
(rec (- n 1)
(lambda (a)
(rec (- n 2)
(lambda (b)
(funcall f (+ a b)))))))))
(rec n #'identity)))
scheme实现
(define (fib n)
(define (iter n f)
(if (= n 1)
(f 0 1)
(iter (- n 1)
(lambda (a b)
(f b (+ a b))))))
(iter n (lambda (n1 n0) n0)))
(define (fib n)
(define (rec n f)
(if (<= n 2)
(f 1)
(rec (- n 1)
(lambda (a)
(rec (- n 2)
(lambda (b)
(f (+ a b))))))))
(rec n (lambda (a) a)))
结论
跑一下上面五段程序就会发现，虽然都是cps风格的尾递归程序（纠正：应该是尾调用（tail call）程序），但是在一些语言中仍然会栈溢出：
scala支持尾递归的注解，但是并非强制实现。从结果来看迭代的cps可以被优化，但是双路递归的不行；kotlin则是用tailrec关键字来强制检查优化。表现和scala相同，但是双路递归的cps写法仍然是尾递归，但是kotlin的语言处理程序却无法接受，没法优化，还暴出警告。common lisp是编译的时候默认做尾递归优化，但是仍然无法优化双路递归的cps写法。看下来只有scheme版本在chezscheme环境中支持双路递归的cps写法。
回想起来，很多宣称尾递归优化的语言所做的大都是把递归换成循环，但不能用同样的方法来优化双路递归的代码。或许chezscheme是从根本解决这个问题的吧，不知道它是如何处理的。
推荐阅读
发表评论