我被教导了一种使用 mod 和递归计算指数的不同方法，但我并不完全理解它。方法是：要做b^e，我们可以这样分解：
q = e div 2
r = e mod 2
then e = 2q+r, and r could be 0 or 1.
If r=0:
b^e = (b^q)^2
If r=1:
b^e = (b^q)^2 * b
base case: b^0 = 1.
例如：2^2, b=2, e=2。
q = 2/2 = 1
r = 2mod2 = 0
r=0, therefore 2^2 = 2^1^2
我正在尝试对此进行编码。
pow :: Integer -> Integer -> Integer
pow b e
| e == 0 = 1
| r == 0 = pow (pow b q) 2
| r == 1 = b * pow (pow b q) 2
where
(q, r) = divMod e 2
但是代码不会在任何时候结束e!=0，例如，pow (-2) 4或者pow 1 1永远持续下去。知道为什么吗？
如果您尝试pow b 2手动评估，您会很快明白原因。因为divMod 2 2 = (1, 0)，我们从 扩展pow b 2到pow (pow b 1) 2。请注意，这也是形式pow b' 2，b' = pow b 1。所以我们得到了一个无限链：
pow b 2
=
pow (pow b 1) 2
=
pow (pow (pow b 1) 1) 2
=
pow (pow (pow (pow b 1) 1) 1) 2
=
...
有几种方法可以解决它。你可以添加一个基本情况为e == 2，或代替递归调用pow两次，你可以只是自己做乘法（如更换pow foo 2与foo * foo您现有的代码）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句