这个特定的递归可以用尾部优化的方式重写吗？

Question

phi n 0 = 1
phi n l = 1 + 1 / phi n (l - 1)

显然，最后评估的动作 不是 递归调用，因此给定的实现确实会抛出足够大的 l.

那么有什么方法（如果有的话）重写递归，使 1) 它保持递归，2) 变成尾部优化？我假设 phi n l result 会起作用，但是不能相应地重新定义...是否有可靠的 methods/techniques 如何解决此类问题？

Answer 1

所以你有这个计算树：

               +                 l
              ╱ ╲
             1   ÷
                ╱ ╲
               1   +             l-1
                  ╱ ╲
                 1   ÷
                    ╱ ╲
                   1  ...
                        ╲
                         +       1
                        ╱ ╲
                       1   ÷
                          ╱ ╲
                         1   1   0

由于它具有线性形状，您确实可以使其成为尾递归的。为此，您需要从底部开始，并将已经计算出的正确结果保存在累加器变量中。

phi _ l = go 0 1  -- n isn't actually used
 where go l' acc
        | l' < l     = go (l'+1) $! 1 + 1/acc
        | otherwise  = acc

未测试，此处可能存在 off-by-1 错误。