这个低效的(树递归)fib(n)
函数计算第n个斐波那契数。在Haskell中:
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)
使用以下公式:
gfib(n) = (fib(n), fib(n+1))
我们可以合成一个线性递归版本:
fib n = fst (gfib n)
where gfib 0 = (0, 1)
gfib n = (b, a + b)
where (a, b) = gfib (n - 1)
另一方面,有一个众所周知的尾递归版本:
fib n = go n 0 1
where go 0 a b = a
go n a b = go (n - 1) b (a + b)
现在的问题是:
有没有一种方法可以使用Burstall&Darlington的折叠/展开技术从线性递归版本合成尾递归版本? 我的目标是了解如何转换线性递归程序,以便将返回的元组转换为两个累积参数,使得生成的程序为尾递归。
上下文:函数式编程、程序综合/派生、程序转换、归纳
g n = f (g (n-1))
(和一个基本情况)的递归可以使用累加器进行转换go n x = go (n-1) (f x)
。最终,我们在两种情况下都计算f.f.f. ... $ base
,一种从左边开始,另一种从右边开始。 - chi