Haskell – Recursion Stack Overflow

  • A+
Category:Languages

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))) 

 


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.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: