How do I avoid stackoverflow error in Haskell

Question

I want to make this Function:

calling customPower 2 2 would give back 2^2 + 2^1 + 1

calling customPower 3 3 would give back 3^3 + 3^2 + 3^1 + 1

Here is my code:

customPower :: Int -> Int -> Int
customPower x y
          | y == 0 = 1
          | y > 0 = (x^(y)) + (customPower x y-1)

It gives me stack overflow exception and I can't find where is the error. Everything seems fine.

Answer 1

The operators have lower precedence than function calls, this means that your recursive call:

... + (customPower x y-1)

is interpreted as:

... + ((customPower x y)-1)

so you keep calling with the same parameters, therefore the recursion can never end.

We can fix this by adding brackets for y-1:

customPower :: Int -> Int -> Int
customPower x y
    | y > 0 = x^y + customPower x (y-1)
    | otherwise = 1

With this modifications, we do not get stuck in an infinite loop:

Prelude> customPower 5 3
156 

We can rewrite the above by making use of sum :: Num a => [a] -> a and map :: (a -> b) -> [a] -> [b] to implement this with a one-liner:

customPower :: (Num a, Integral b) => a -> b -> a
customPower x y = sum (map (x^) [0..y])

or we can use iterate :: (a -> a) -> a -> [a]:

customPower :: (Num a, Integral b) => a -> b -> a
customPower x y = sum (take (y+1) (iterate (x*) 1))

Due to Haskell's laziness, the above attempts will likely still result in a call stack that scales linear with the value of y: the functions are, like @dfeuer says, not tail recursive functions, we can however work with an accumulator here:

customPower :: Int -> Int -> Int
customPower x = go 1
    where go a y | y > 1 = a
                 | otherwise = seq a (go (a+x^y) (y-1))

since the above sum is equal to a simple formula, we can even calculate the value in O(y log x):

   y
.————            y+1
 ╲     i       x    - 1
 ╱    x    =   ————————
*————            x - 1
  i=0

So we can calculate the value with:

customPower :: (Integral a, Integral b) => a -> b -> a
customPower x y = div (x^(y+1) - 1) (x - 1)

This will usually work faster, although in a rare case where the result times x -1 is larger than the maximum representable number of the type a, this will result in overflow and will return the wrong number.