Haskell递归栈溢出

Question

我是 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 + 1。这是著名的 Collatz 问题的一部分。

Answer 1

函数应用程序的优先级高于许多其他操作，因此 foo 3 * x + 1 实际上是调用 foo 3，然后将该结果乘以 x 并添加 1，看起来就像你的无限循环可能在哪里。

将其更改为以下内容应该可以解决这个问题：

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

Haskell递归栈溢出

Haskell recursion stack overflow

stack-overflow

recursion

haskell

guard