Stack overflow in my recursive function

Question

Code is here , when i call numberOf 3 or numberOf integer>2 im getting this error ERROR - C stack overflow . My code should change numbers between 2^(n-2) (2^n)-1 for n>2 to Binary and check if is there consecutive 0 or not . If is there dont count and if there isnt +1 .

numberOf :: Integer -> Integer  
numberOf i = worker i

worker :: Integer -> Integer  
worker i  
    | (abs i) == 0 = 0   
    | (abs i) == 1 = 2  
    | (abs i) == 2 = 3   
    | otherwise = calculat (2^((abs i)-2)) ((2^(abs i))-2)

calculat :: Integer -> Integer -> Integer  
calculat ab bis  
    | ab == bis && (checker(toBin ab)) == True = 1  
    | ab < bis && (checker(toBin ab)) == True = 1 + (calculat (ab+1) bis)  
    | otherwise =  0 + (calculat (ab+1) bis)  

checker :: [Integer] -> Bool  
checker list  
    | list == [] = True  
    | 0 == head list && (0 == head(tail list)) = False  
    | otherwise = checker ( tail list)  

toBin :: Integer -> [Integer]  
toBin n  
   | n ==0 = [0]  
   | n ==1 = [1]  
   | n `mod` 2 == 0 = toBin (n `div` 2) ++ [0]  
   | otherwise = toBin (n `div` 2) ++ [1]

Tests :

numberOf 3 Answer:(5)
numberOf 5 (13)
numberOf 10 (144)
numberOf (-5) (13)

(+1) for stack overflow in the title.

גלעד ברקן
– גלעד ברקן

2014-11-10 16:10:23 +00:00
Commented Nov 10, 2014 at 16:10 — גלעד ברקן
– גלעד ברקן, Commented Nov 10, 2014 at 16:10

bheklilr · Accepted Answer · 2014-11-10 00:12:22Z

The problem lies with your definition of calculat. You have the cases of ab == bis and ab < bis, but the only place you call calculat is from worker with the arguments 2^(abs i - 1) and 2^(abs i - 2). Since the first number (ab) will always be larger than the second (bis), checking for ab < bis is pretty silly. In your otherwise condition you then increment ab, ensuring that this function will never terminate. Did you instead mean otherwise = calculat ab (bis + 1)?

You could also clean your code up substantially, there are many places where you've done things the hard way, or added unnecessary clutter:

-- Remove worker, having it separate from numberOf was pointless
numberOf :: Integer -> Integer
numberOf i
    | i' == 0 = 0
    | i' == 1 = 2
    | i' == 2 = 3
    -- Lots of unneeded parentheses
    | otherwise = calculat (2 ^ (i' - 1)) (2 ^ i' - 2)
    -- Avoid writing the same expression over and over again
    -- define a local name for `abs i`
    where i' = abs i

calculat :: Integer -> Integer -> Integer
calculat ab bis
    -- Remove unneeded parens
    -- Don't need to compare a boolean to True, just use it already
    | ab == bis && checker (toBin ab) = 1
    | ab <  bis && checker (toBin ab) = 1 + calculat (ab + 1) bis
    -- 0 + something == something, don't perform unnecessary operations
    | otherwise                       = calculat (ab + 1) bis

-- Pattern matching in this function cleans it up a lot and prevents
-- errors from calling head on an empty list
checker :: [Integer] -> Bool
checker []      = True
checker (0:0:_) = False
checker (_:xs)  = checker xs

-- Again, pattern matching can clean things up, and I find an in-line
-- if statement to be more expressive than a guard.
toBin :: Integer -> [Integer]
toBin 0 = [0]
toBin 1 = [1]
toBin n = toBin (n `div` 2) ++ (if even n then [0] else [1])

i wanna check all numbers between 2^((abs i)-2) and (2^(abs i))-2 . this was my false . Sorry for that now i got this problem : Program error: pattern match failure: head []
This is because you're calling head (tail list), and list might only have one element. In general, you should prefer pattern matching over using head and tail, I'll edit my post to show your code cleaned up.
Thank you very much , im just beginner at haskell and im not good yet. i dont know yet which code is unneeded or needed . Thank you again for your advices in code.
By test case numberOf 20 , it takes longer time and get C stack overflow error . Have you another advice for it ?
@Mert For numberOf 20, you're going to be checking every single number between 2^18 and 2^20-2, or a total of 786430 numbers. Your toBin and checker functions are not particularly efficient as lists aren't the right data structure to use here (Data.Sequence.Seq might be a better choice, Data.Vector.Vector would be the best). You could also consider using Data.Bits and some fancy boolean logic to help, it's almost certainly faster than doing it yourself.

ditoslav · Accepted Answer · 2014-11-10 00:03:24Z

0

In calculat in case ab == bis but checker returns false you cant return from the function.

How about:

| ab >= bis && (checker(toBin ab)) == True = 1
| ab < bis && (checker(toBin ab)) == True = 1 + (calculat (ab+1) bis)  
| otherwise =  0 + (calculat (ab+1) bis)  
| ab >= bis = 0  
| ab < bis == True = 0 + (calculat (ab+1) bis)  
| otherwise =  0 + (calculat (ab+1) bis)

edited Nov 10, 2014 at 0:03

answered Nov 9, 2014 at 23:36

ditoslav

4,91811 gold badges55 silver badges89 bronze badges

2 Comments

Mert Over a year ago

add ab== bis and checker false condition but still stack overflow

Mert Over a year ago

now i got: Program error: pattern match failure: head [] with this code | ab >= bis && (checker(toBin ab)) == True = 1 | ab < bis && (checker(toBin ab)) == True = 1 + (calculat(ab+1) bis) | ab < bis = 0 + (calculat (ab+1) bis) | otherwise = 0 + (calculat (ab+1) bis)

Collectives™ on Stack Overflow

Stack overflow in my recursive function

2 Answers 2

5 Comments

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

2 Comments

Related