我对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)上,它中断。有人能向我解释一下吗?这样我将来就可以避免它了。
2条答案
按热度按时间toiithl61#
函数式语言中的堆栈溢出通常意味着:无界递归。实际上,对于大量的输入,这就是这里所发生的:以
digitSum 2 0
为例,它与第一个模式匹配不匹配,所以它进行第二个模式匹配,即base=2
和x=0
、x
modbase = 1
和x
divbase = 0
,然后递归调用digitSum 2 0
,然后永远调用。这是因为您的基本案例是错误的:它应该是
digitSum _ 0 = 0
,因为如果你用整数x
除以base
,如果base
不是1
,你最终总是得到0
。vddsk6oq2#
BlackBeans has the right answer,但作为补充,堆栈溢出不仅可能出现在无限递归上,也可能出现在 * 太多 * 递归上。幸运的是,这很容易通过以尾递归的方式编写函数来解决。如果你这样做,你的Haskell编译器就可以在恒定的堆栈空间中运行函数。
实现这一点的常见方法是添加累加器参数,而这通常对具有本地函数的函数的用户是隐藏的。
如果您以尾部递归样式编写函数 * 并且 * 具有无限递归,则不要期望看到堆栈溢出,但要期望看到程序只是挂起,因为递归没有终止。