我在 Python 中通过平方算法实现了求幂
(x,n)=(input(),input())
def exp_itr(x,n):
r=1
while n!=0:
if n%2==1:
r=r*x
n=n-1
x=x*x
n=n/2
return r
现在,我需要递归算法。我该怎么做?
我在 Python 中通过平方算法实现了求幂
(x,n)=(input(),input())
def exp_itr(x,n):
r=1
while n!=0:
if n%2==1:
r=r*x
n=n-1
x=x*x
n=n/2
return r
现在,我需要递归算法。我该怎么做?
这是评论中提到的伪代码的 Python 版本
def exp(x, n):
if n < 0:
return exp(1 / x, -n)
elif n == 0:
return 1
elif n == 1:
return x
elif n % 2 == 0:
return exp(x * x, n / 2)
else:
return x * exp(x * x, (n - 1) / 2)