Можно ли переписать эту конкретную рекурсию оптимизированным для хвостов способом?

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

Не тестировалось, здесь может быть ошибка off-1.