Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Haskell - Recursion Stack Overflow

I am trying to sum all n from 1 to a very large number (10**9 for now) but it gives stack overflow. Also I don't think putting a stop at 1 and doing the sum n in different rows is the most efficient way but the code below is all my knowledge for Haskell. I really don't know much about functional programming and I would like as much explanation as possible. (Also I have tried putting $! strict in the last line which was told in other places but it changed nothing. I would be glad if you explained the most efficient way I could do this recursive function.)

main :: IO()

summ 1 = 1
summ n = 1/(n**2) + summ (n-1)

expected_value = pi*pi/6
errorPercent n = n / expected_value * 100

main = do
    putStr "%"
    print (errorPercent (summ $! (10**9)))
like image 438
Terobero Avatar asked Dec 02 '22 10:12

Terobero


1 Answers

chi has answered one bit of the question, which I think is the main problem, but there is something else that is bugging me. When you say 10**9, you get a floating point number (because ** is "fractional" exponentiation). And then you are using floating point equality to check for the base case of your recursion.

summ 1 = ...

The problem with this is that it is possible, and as the argument gets larger, likely, that because of numerical error you will just barely miss the base case and descend into negative values forever.

summ 4 =        ... summ 3
summ 3 =        ... summ 2.000001
summ 2.000001 = ... summ 1.000001 
summ 1.000001 = ... summ 0.000001  -- BASE CASE MISSED!
summ 0.000001 = ... summ (-1.000001)
summ (-1.000001) = ... summ (-2.000001)

and so on. If you didn't get a stack overflow from 109 calls, you surely will with infinitely many.

You should either define your function on integers so there is no rounding error

summ :: Int -> Double
summ 1 = 1
summ n = 1 / (fromIntegral n ** 2) + summ (n - 1)
--            ^^^^^^^^^^^^
-- conversion necessary to go from Int to Double

main = ... print (summ (10 ^ 9))
--                      ^^^^^^
--      use integral exponentiation (^) instead of (**)

or use a more forgiving base case

summ :: Double -> Double
summ n | n <= 1 = 1
summ n = 1 / (n ** 2) + summ (n - 1)

In either case, you should definitely take chi's suggestion to do this in accumulator style, and you should also definitely put a type signature.

Here's more on how you get stack overflows in Haskell if you are curious.

like image 82
luqui Avatar answered Dec 30 '22 18:12

luqui