这种特定的递归能否以尾部优化的方式重写？

Question

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

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

那么重写递归的方式是什么(如果有的话)1)它仍然是递归的,2)变得尾部优化？我认为phi n l result可以工作,但不能相应地重新定义...是否有可靠的方法/技术如何解决这样的问题？

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

未经测试,此处可能存在一个1分之一的错误.