Haskell函数导致堆栈溢出

Question

我对 Haskell 比较陌生，并且总体上对编程缺乏经验。一个函数在某些输入上导致堆栈溢出，我不知道为什么。

有问题的函数：

digitSum :: Integer -> Integer -> Integer
digitSum _ 1 = 1
digitSum base x = (x `mod` base) + digitSum base (x `div`base)

在某些输入（例如 10 15、11 121、16 19、3 1234）上它可以工作，而在其他输入（例如 10 456）上它会中断有人可以向我解释一下这一点，以便我将来可以避免它吗？

Answer 1

函数式语言中的堆栈溢出通常意味着：无界递归。事实上，对于很多输入来说，这就是这里发生的情况：以 为例digitSum 2 0。它与第一个模式匹配不匹配，因此适用于第二种情况，即base=2and x=0。x `mod` base = 1和x `div` base = 0。然后它会递归调用digitSum 2 0. 然后永远。

这是因为你的基本情况是错误的：它应该是digitSum _ 0 = 0，因为如果你保持整数除以x，base如果base不是1，你总是会得到0。