编写一个高效的递归幂函数
创始人
2024-12-06 09:30:50
0

下面是一个高效的递归幂函数的代码示例:

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

这个递归幂函数利用了以下原理:

  • 当指数为0时,任何数的0次方都等于1,所以返回1作为递归终止条件。
  • 当指数为1时,任何数的1次方都等于其本身,所以返回该数作为递归终止条件。
  • 当指数为奇数时,可以将其拆分为一个偶数指数和一个多出来的底数,例如3的5次方可以表示为3的4次方乘以3,即3^5 = 3^4 * 3。这样就可以利用递归函数计算出3的4次方,然后再乘以3,从而减少了递归的次数。
  • 当指数为偶数时,可以将其拆分为两个相同的偶数指数,例如4的6次方可以表示为4的3次方乘以4的3次方,即4^6 = 4^3 * 4^3。这样就可以利用递归函数计算出4的3次方,然后将结果相乘,减少了递归的次数。

这个递归幂函数的时间复杂度为O(logn),其中n为指数大小。因为每次递归都将指数减半,所以递归的次数为logn。

相关内容

热门资讯

wepoke插件!wepoke... wepoke插件!wepoke小技巧,wEPoke其实真的有挂,2025新版教程(有挂攻略);实战中...
微扑克ai辅助工具!微扑克全自... 微扑克ai辅助工具!微扑克全自动机器人,微扑克辅助钻石,详细教程(有挂规律)1、每个玩家都可以进行使...
重大通报!约战丹东麻将有挂么(... 重大通报!约战丹东麻将有挂么(透视)其实是有挂(2021已更新)(哔哩哔哩);1、约战丹东麻将有挂么...
软件教程!wepok软件透明挂... 1、软件教程!wepok软件透明挂(wepoke辅助机器人)wePoke(一般真的有挂);详细教程。...
微扑克ai辅助!微扑克有辅助,... 微扑克ai辅助!微扑克有辅助,wpk微扑克真的有辅助插件,必赢方法(有挂秘籍);微扑克辅助插件是一个...
揭秘攻略!哈灵棋牌有软件挂吗(... 揭秘攻略!哈灵棋牌有软件挂吗(辅助)切实真的有挂(2026已更新)(哔哩哔哩)1、用户打开应用后不用...
wepoke辅助!wepoke... wepoke辅助!wepoke计算辅助,wEPOKE一般真的有挂,切实教程(有挂工具);wEPOKE...
微扑克ai辅助器苹果版!微扑克... 1、微扑克ai辅助器苹果版!微扑克软件开发定制app(辅助挂)一贯是真的有挂;详细教程。2、微扑克透...
一分钟揭秘!兴动竞技app有挂... 一分钟揭秘!兴动竞技app有挂吗(辅助)切实存在有挂(2021已更新)(哔哩哔哩)所有人都在同一条线...
安装教程!wepower让系统... 安装教程!wepower让系统发好牌(wepoke真的有挂)wepOKE(其实真的有挂);大神普及一...