@[TOC](2.22学堂在线python笔记，递归)
# 知识点
1. 汉诺塔问题为了计算实际上移动整个塔到另一个塔的实际步数，用迭代的方式思考非常困难，但是一旦用递归的方式思考问题就变得相当简单了。
2. 只要一开始把n个圆盘移动到另一个柱子的问题简化成：将n-1个圆盘移动到另一个柱子，并且最后把一个圆盘移动到那个柱子上即可。找到基线条件
```py
def printMove(fr,to):
print('move from',str(fr),'to',str(to))
#首先要理解Tower函数的主要功能
#就是把这些圆环整个一起抬起来从fr移到to这个柱子上
def Towers(n,fr,to,spare):
if n==1:
printMove(fr,to)
else:
Towers(n-1,fr,spare,to)
#这就相当于把前n-1个圆环整个抬起来放到spare
#这根柱子上
Towers(1,fr,to,spare)
#然后再把fr剩下的圆环放到to上
Towers(n-1,spare,to,fr)
#最后把spare剩下的圆环放到to上，刚好顺序正确
```
3. 计算斐波那契数列的第n项值，可以看到，`assert`的作用在于其中的值为真的时候才会运行代码块，否则会返回一个assertionerror进而结束程序。
```py
def getfib(n):
'''
输入斐波那契数列的长度n
得到斐波那契数列的第n项
'''
assert n>=0 and type(n)==int
if n<=2:
return 1
while n>2:
return getfib(n-1)+getfib(n-2)
```
4. 将递归算法用到非数字例子当中去
例如，字符串操作，给定一个字符串，我们怎么知道它是否是回文结构palindrome
回文结构即从左往右和从右往左读是相同意义
```py
def isPalindrome(s):
def toChar(s):
'''
输入一个字符串s，将字符串s的所有标点符号去除
并且转化为小写的形式
'''
ans=''
s=s.lower()
c=''
for c in s:
if c in 'abcdefghijklmnopqrstuvwxyz':
ans=ans+c
return ans
def isPal(s):
if len(s)<=1:
return True
else:
return s[0]==s[-1] and isPal(s[1:-1])
#特别要注意这里的切片工作，从1开始但是切掉了-1
# if s[0]==s[-1]:
# return isPal(s[1:-1])
# else:
# return False
return isPal(toChar(s))
```
注意这里有精彩的应用，即在一个函数体当中定义两个不同的函数，最后需要两个不同函数来返回最终的总函数值，这就意味着在递归的时候可以仅递归某个子函数即可。
5. 分治法的介绍，将原来的大问题拆分成比原来的大问题刚好简单一点点的小问题来解决
# 做题
1. In Problem 1, we computed an exponential by iteratively executing successive multiplications. We can use the same idea, but in a recursive function.
Write a function recurPower(base, exp) which computes baseexp by recursively calling itself to solve a smaller version of the same problem, and then multiplying the result by base to solve the initial problem.
This function should take in two values - base can be a float or an integer; exp will be an integer ≥0. It should return one numerical value. Your code must be recursive - use of the ** operator or looping constructs is not allowed.
在这里要想办法用递归算法来实现正幂次计算，即定义函数recurPower（base，exp）来计算
base^exp^
注意到怎么设定基线条件？
那就是你的exp最小是什么能够直接解决？
这里exp显然只有exp=0能够直接就解决，所以在设定基线条件的时候应该设定好exp=0
```py
def recurPower(base,exp):
if exp<=0:
return 1
while exp>0:
return recurPower(base,exp-1)
```
2. 使用第二种基线条件来完成这个递归
```py
def recurPowerNew(base,exp):
if exp<=0:
return 1
if exp%2==0:
return recurPowerNew(base*base,exp/2)
else:
return base*recurPowerNew(base,exp-1)
```
注意到要求base^exp^
3. 找两个正整数中，最大公约数
用迭代算法求gcdIter(a,b)可能考虑是从min（a，b）开始往下减1，并且测试是否全部整除a，b
但是递归算法算gcdRecur(a,b)使用了欧几里得算法这种更聪明的形式
当b=0，那么最大公约数就是a
当b≠0，那么最大公约数是gcdRecur(b,a % b)
```py
def gcdRecur(a,b):
if b<=0:
return a
while b>0:
return gcdRecur(b,a%b)
```
网友评论