How do you make this Haskell power function tail recursive?

Question

turboPower a 0 = 1
turboPower a b
    | even b = turboPower (a*a) (b `div` 2)
    | otherwise = a * turboPower a (b-1)

THANKS!

Answer 1

turboPower a b = turboPower' 1 a b
  where
    turboPower' x a 0 = x
    turboPower' x a b
        | x `seq` a `seq` b `seq` False = undefined
        | even b = turboPower' x (a*a) (b `div` 2)
        | otherwise = turboPower' (x*a) a (b-1)

Basically, what you want to do is move the multiplication that you're doing in the "otherwise" step (since that's what keeps this from being tail-recursive initially) to another parameter.

Edited to add a line making all three parameters strictly evaluated, instead of lazy, since this is one of those well-known situations where laziness can hurt us.