本文讲述了python基础编程100例：第90期-基础算法：递归 Pow(x, n)！具有很好的参考价值，希望对大家有所帮助。一起跟随六星小编过来看看吧，具体如下:

第90期-基础算法：递归 Pow(x, n)

1 问题描述

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。

示例 1:

输入: x = 2.00000, n = 10

输出: 1024.00000

示例 2:

输入: x = 2.10000, n = 3

输出: 9.26100

示例 1:

输入: x = 2.00000, n = -2

输出: 0.25000

解释: 2**-1 = 1/2**2 = 1/4 = 0.25

初始代码

from typing import List

class Solution:

    def myPow(self, x: float, n: int) -> float:

        #在此之间填写代码

print(Solution().myPow(2.0,10))

print(Solution().myPow(2.1,3))

print(Solution().myPow(2.0,-2))

2 解题思路

标签：快速幂 + 递归

「快速幂算法」的本质是分治算法。举个例子，如果我们要计算 x^{64}，我们可以按照：

从 xx 开始，每次直接把上一次的结果进行平方，计算 66 次就可以得到 x^{64}的值，而不需要对 xx 乘 6363 次 xx。

再举一个例子，如果我们要计算 x^{77}，我们可以按照：

直接从左到右进行推导看上去很困难，因为在每一步中，我们不知道在将上一次的结果平方之后，还需不需要额外乘 xx。但如果我们从右往左看，分治的思想就十分明显了：

当我们要计算 x^n 时，我们可以先递归地计算出 y = x^[n/2]其中[a]表示对 a 进行下取整；

根据递归计算的结果，如果 n 为偶数，那么 x^n = y^2 ；如果 n 为奇数，那么 x^n = y^2 *x；

递归的边界为 n = 0，任意数的 0 次方均为 1。

3 解题方法

from typing import List

class Solution:

    def myPow(self, x: float, n: int) -> float:

        def quickMul(N):

            if N == 0:

                return 1.0

            y = quickMul(N // 2)

            return y * y if N % 2 == 0 else y * y * x

        

        return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)

print(Solution().myPow(2.0,10))

print(Solution().myPow(2.1,3))

print(Solution().myPow(2.0,-2))

第1-3，12-14行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑

第4行： 创建quickMul函数

第5-6行： 结束条件：当N=0时，返回1.0（任意数的0次方都为1）

第7行： 定义变量y为N除以二的整数部分的递归结果

第8行： 若N整除2，则直接返回yy,否则返回yy*x

第10行： 当n>=0时，利用quickMul函数返回结果，否则，返回-n情况下的倒数

代码运行结果为：

算法讲解

这里用到了基础算法：递归，简单讲解下这个算法：

什么是递归

程序调用自身的编程技巧称为递归

递归做为一种算法在程序设计语言中广泛应用。

递归算法一般用于解决三类问题：

(1)数据的定义是按递归定义的。（Fibonacci函数）

(2)问题解法按递归算法实现。

(3)数据的结构形式是按递归定义的。

递归函数特征

必须有一个明确的结束条件；

每次进入更深一层递归时，问题规模相比上次递归都应有所减少

相邻两次重复之间有紧密的联系，前一次要为后一次做准备（通常前一次的输出就作为后一次的输入）。

递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出）

更多相关技术内容咨询欢迎前往并持续关注六星社区了解详情。

如果你想用Python开辟副业赚钱，但不熟悉爬虫与反爬虫技术，没有接单途径，也缺乏兼职经验
关注下方微信公众号：Python编程学习圈，获取价值999元全套Python入门到进阶的学习资料以及教程，还有Python技术交流群一起交流学习哦。