使用Burstall和Darlington的折叠/展开系统从线性递归版本推导出尾递归斐波那契数列。

Question

这个低效的（树递归）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的折叠/展开技术从线性递归版本合成尾递归版本？ 我的目标是了解如何转换线性递归程序，以便将返回的元组转换为两个累积参数，使得生成的程序为尾递归。

上下文：函数式编程、程序综合/派生、程序转换、归纳

- Ricardo Pérez

---

我不知道B＆D技术，但我相信形式为g n = f (g (n-1))（和一个基本情况）的递归可以使用累加器进行转换go n x = go (n-1) (f x)。最终，我们在两种情况下都计算f.f.f. ... $ base，一种从左边开始，另一种从右边开始。 - chi

Answer 1

那个转换被称为"累积"（例如在Bird和Gibbons的《Haskell算法设计》中）。

fib n = fst (go n)
    where go 0 = (0, 1)
          go n = (b, a + b)
              where (a, b) = go (n - 1)

积累中：

fib n = fst (go n (0, 1))
    where go 0 (a, b) = (a, b)
          go n (a, b) = go (n - 1) (b, a + b)

尽管需要注意的是，在这种情况下，累加很容易，因为无论您是向上还是向下计数（n实际上并未被使用）。但是一般情况下，您应该确保生成的函数仍然正确。

然后，要达到所需的实现，您需要应用另外两个简单的转换：

将fst推入（我不知道这是否是一个常见的名称）：

fib n = go n (0, 1)
    where go 0 (a, b) = a
          go n (a, b) = go (n - 1) (b, a + b)

柯里化：

fib n = go n 0 1
    where go 0 a b = a
          go n a b = go (n - 1) b (a + b)

- Noughtmare

---

谢谢你，@noughtmare。虽然这不是我所要求的（因为该解决方案并未使用折叠/展开技术），但它帮助我很多，让我了解如何从一个版本转换到另一个版本。 - Ricardo Pérez