作者:落了个小妞农_602 | 来源:互联网 | 2022-12-01 17:15
我想做这个功能:
调用customPower 2 2
将返回2 ^ 2 + 2 ^ 1 + 1
调用customPower 3 3
将返回3 ^ 3 + 3 ^ 2 + 3 ^ 1 + 1
这是我的代码:
customPower :: Int -> Int -> Int
customPower x y
| y == 0 = 1
| y > 0 = (x^(y)) + (customPower x y-1)
它给我堆栈溢出异常,我找不到错误在哪里.一切似乎都很好.
1> Willem Van O..:
运算符的优先级低于函数调用,这意味着您的递归调用:
... + (customPower x y-1)
被解释为:
... + ((customPower x y)-1)
所以你继续用相同的参数调用,因此递归永远不会结束.
我们可以通过添加括号来解决这个问题y-1
:
customPower :: Int -> Int -> Int
customPower x y
| y > 0 = x^y + customPower x (y-1)
| otherwise = 1
通过这些修改,我们不会陷入无限循环:
Prelude> customPower 5 3
156
我们可以通过使用sum :: Num a => [a] -> a
和map :: (a -> b) -> [a] -> [b]
实现这一点来重写上述内容:
customPower :: (Num a, Integral b) => a -> b -> a
customPower x y = sum (map (x^) [0..y])
或者我们可以使用iterate :: (a -> a) -> a -> [a]
:
customPower :: (Num a, Integral b) => a -> b -> a
customPower x y = sum (take (y+1) (iterate (x*) 1))
由于Haskell的懒惰,上面的尝试可能仍然会导致调用堆栈与以下值的线性比例y
:函数,如@dfeuer所说,不是尾递归函数,但我们可以在这里使用累加器:
customPower :: Int -> Int -> Int
customPower x = go 1
where go a y | y > 1 = a
| otherwise = seq a (go (a+x^y) (y-1))
由于上面的和等于一个简单的公式,我们甚至可以计算O(y log x)中的值:
y
.———— y+1
? i x - 1
? x = ————————
*———— x - 1
i=0
所以我们可以用以下公式计算价值:
customPower :: (Integral a, Integral b) => a -> b -> a
customPower x y = div (x^(y+1) - 1) (x - 1)
这通常会更快,但在极少数情况下,结果时间x -1
大于类型的最大可表示数a
,这将导致溢出并返回错误的数字.