建立一个有效的递归幂函数
建立一个有效的递归幂函数
提问于 2019-05-09 03:46:48
我需要一个函数幂(x，n)，它在n/2步骤中计算x^n。
我创建了一个递归函数，它可以在n步内计算幂：
def simple_recursive_power(x, n):
if n == 0:
return 1
return x * simple_recursive_power(x, n-1)但是，我需要将所需步骤的数量减半(为n/2)。我认为我需要使用‘快速供电’，但我不知道如何实现这个使用递归。
谢谢你的帮助。
回答 2
Stack Overflow用户
回答已采纳
发布于 2019-05-09 03:50:59
您可以根据偶数或奇数拆分数字，当拆分为偶数时，可以将数字拆分为两部分：
def simple_recursive_power(x, n):
if n == 0:
return 1
if n % 2:
return x * simple_recursive_power(x, n - 1)
else:
m = simple_recursive_power(x, n // 2)
return m * mStack Overflow用户
发布于 2019-05-09 03:59:08
我把我的第一个答案放在最后，我的第一个回答是毫无意义的。我研究过renac的答案，这是最好的递归方法。我不明白为什么要使用递归：
def simple_recursive_power(x, n):
if n == 0:
return 1
if n % 2:
return x * simple_recursive_power(x, n - 1)
else:
m = simple_recursive_power(x, n // 2)
return m * m
start = time.time()
a =simple_recursive_power(11, 5000000)
end = time.time()
print((end - start), ' s')
def simple_recursive_power(x, n):
if n == 0:
return 1
if n % 4:
return x * simple_recursive_power(x, n - 1)
else:
m = simple_recursive_power(x, n // 4)
return m * m * m * m
start = time.time()
b = simple_recursive_power(11, 5000000)
end = time.time()
print((end - start), ' s')
start = time.time()
c = 11**5000000
end = time.time()
print((end - start), ' s')研究结果如下：
- 3.190255641937256秒
- 5.789834022521973秒
- 3.141327142715454秒
11**5000000 更容易理解，比递归更快，为什么不使用它呢?
这是因为某些处理器体系结构可以很好地使用递归吗？
唯一的办法必须是多处理，或线程！
我的第一个回答是：
我不明白重点，但是..。这应该是可行的：
def simple_recursive_power(x, n):
if n == 0:
return 1
elif n == 1:
return x
return x * x * simple_recursive_power(x, n - 2)编辑: n/3步骤：
def simple_recursive_power(x, n):
if n == 0:
return 1
elif n == 1:
return x
elif n == 2:
return x * x
return x * x * x simple_recursive_power(x, n - 3)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/56051873
复制相关文章
相似问题
腾讯云开发者
