# 第90期-基础算法：递归 Pow(x, n)
Python是一门需要不断实践练习的编程语言，本文档将AI大学堂学员交流群的Python每周练习进行汇总，希望各位小伙伴能够多进行实践练习，逐渐爱上这门神奇的编程语言，掌握它并在生活中能够使用它。
# 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
3
4
5
6
7
8
# 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))
2
3
4
5
6
7
8
9
10
11
12
13
14
第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）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出）
# 4 视频解析
高清视频讲解，请查看AI大学堂Python基础实战100例 (opens new window)
关注『讯飞AI大学堂』公众号，发送 python100 即可领取Python基础实战100例源代码 