我的递归函数中的堆栈溢出

Question

代码在这里,当我调用numberOf 3或numberOf整数> 2我得到此错误ERROR - C堆栈溢出.我的代码应该将2 ^(n-2)(2 ^ n)-1之间的数字更改为n> 2到二进制,并检查是否有连续的0.如果有不计数,如果没有+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]    

测试:

numberOf 3答案:(5)
numberOf 5(13)
numberOf 10(144)
numberOf(-5)(13)

Answer 1

问题在于你的定义calculat.你的情况ab == bis和ab < bis,但你所说的唯一的地方calculat是worker与参数2^(abs i - 1)和2^(abs i - 2).由于第一个数字(ab)总是大于第二个(bis),因此检查ab < bis非常愚蠢.在您的情况下,然后递增ab,确保此功能永远不会终止.你的意思是otherwise = calculat ab (bis + 1)？

你也可以大大清理你的代码,有很多地方你已经做了很多事情,或者添加了不必要的混乱:

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