下面是一个高效的递归幂函数的代码示例:
def power(base, exponent):
# 递归终止条件
if exponent == 0:
return 1
elif exponent == 1:
return base
# 如果指数是奇数
elif exponent % 2 != 0:
return base * power(base, exponent - 1)
# 如果指数是偶数
else:
result = power(base, exponent // 2)
return result * result
# 测试
print(power(2, 10)) # 输出: 1024
print(power(3, 5)) # 输出: 243
这个递归幂函数利用了以下原理:
这个递归幂函数的时间复杂度为O(logn),其中n为指数大小。因为每次递归都将指数减半,所以递归的次数为logn。
下一篇:编写一个高效的回溯函数