CODEWITHSUNDEEP
haskellrecursionstack-overflow
Mert
Mert

Reputation: 55

Stack overflow in my recursive function

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)

Upvotes: 0

Views: 135

Answers (2)

bheklilr
bheklilr

Reputation: 54058

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

Upvotes: 5

ditoslav
ditoslav

Reputation: 4872

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)

Upvotes: 0

Related Questions