CODEWITHSUNDEEP
haskellrecursionfunctional-programmingtail-recursion
Zazaeil
Zazaeil

Reputation: 4109

Can this particular recursion be rewritten in a tail-optimized way?

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

Obviously, the last evaluated action is not recursive call, thus given implementation indeed throws with a sufficiently large l.

So what's the way (if any) to rewrite recursion such that 1) it remains recursive, 2) becomes tail-optimized? I assume phi n l result would work, however can't redefine accordingly... are there reliable methods/techniques how to tackle down such a problems?

Upvotes: 3

Views: 138

Answers (1)

leftaroundabout
leftaroundabout

Reputation: 120711

So you have this computation tree:

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

Since this has a linear shape, you can indeed make it tail-recursive. For this you need to start at the bottom and keep the already-calculated right result in an accumulator variable.

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

Not tested, there might be an off-by-1 error here.

Upvotes: 6

Related Questions