Haskell遞歸堆棧溢出

我對Haskell來說很新，所以對於這個問題抱歉。但是 - 如何擺脫無盡的遞歸，並沒有被超越。這是代碼：Haskell遞歸堆棧溢出

foo :: Integer -> Integer 
foo x 
    | x == 1   = 1 
    | x <= 0   = error "negative number or zero" 
    | odd x   = foo 3 * x + 1 
    | x `mod` 2 == 0 = foo x `div` 2 
    | otherwise  = x

編輯：

foo :: Integer -> (Integer, Integer) 
foo x 
    | x == 1   = (1, z) 
    | x <= 0   = error "negative number or zero" 
    | odd x   = foo (3 * x + 1) . inc z 
    | even x   = foo (x `div` 2) . inc z 
    | otherwise  = (x, z) 
    where z = 0 

inc :: Integer -> Integer 
inc i = i + 1

我相信代碼是不言自明，但尚未：如果x是偶數然後將其劃分2另有3 * X +這是着名的Collatz問題的一部分。

來源

2015-05-24 user8

您也可以使用'even'代替'國防部2'測試。而且看起來你的'否則'情況永遠不會達到。 –

在你的編輯中，像'f x。 g y'同夥喜歡'（f x）。（g y）'而不是'（f x。g）y'，因爲函數應用程序的綁定比任何運算符都要緊密。你可以在這裏使用'$'（實際上，你可能將'$'與'''混合在一起），但是你也可以使括號明確，而不是使用'。'或'$'。 –

功能應用具有比許多其他操作的優先級高，所以foo 3 * x + 1實際上是調用foo 3，然後通過x該結果乘以並添加1，它看起來像您的無限循環可能。

將其更改爲以下要解決這個問題：

| odd x   = foo $ 3 * x + 1 
| x `mod` 2 == 0 = foo $ x `div` 2

來源

2015-05-24 00:23:41

你能解釋一下'$'是什麼嗎？ – user8

你也可以把它寫成'f（3 * x + 1）'。請參閱[本文]（http://stackoverflow.com/questions/940382/haskell-difference-between-dot-and-dollar-sign）瞭解更多關於'$'的描述。 –

當我想用'.'來計算'foo'被應用的次數時，我該怎麼辦？它在編輯部分。 – user8

Haskell遞歸堆棧溢出

回答

相關問題