MIT 6.00.1X 计算机科学和PYTHON编程导论-学习笔记（五）递归

133 阅读 0 评论 88 点赞

我是靠谱客的博主如意白猫，这篇文章主要介绍MIT 6.00.1X 计算机科学和PYTHON编程导论-学习笔记（五）递归，现在分享给大家，希望可以做个参考。

迭代：

e.g. 计算 x*p

复制代码

1
2
3
4
5
6
def multi(x,p):
ans=0
while p>0:
ans+=x
p-=1
return(ans)

状态变量（设置初始值）：

迭代次数i

当前计算结果 result

状态变量会在迭代的过程中得到更新。

递归：数学归纳法思想

——把一个复杂问题变成一个稍简单的复杂问题加上/乘上一个简单的计算递归case

——把问题一直简化下去，直到变成一个base case 能够直接得到结果。 base case

e.g. n！=n*（n-1）！=.....

用递归思想做乘法：

复制代码

1
2
3
4
5
def multi(a,b):
if b==1:
return a
else:
return a+multi(a,b-1)

每次调用递归都会创建一个新的环境，包含新的局部变量

当最后一次递归实现后，会一步一步代回被调用的地方

assert函数：

检查输入是否符合假设，符合则执行函数体，否则结束并报错

e.g. 斐波那契数列

复制代码

1
2
3
4
5
6
def fib(x):
assert type(x)==int and x>=0
if x==0 or x==1:
return 1
else:
return fib(x-1)+fib(x-2)

e.g. 回文判定

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def isPalindrome(s):
def toChare(s):
s=s.lower()
ans=''
for c in s:
if c in 'abcdefghijklmnopqrstuvwxyz':
ans+=c
return ans
def isPal(s):
if len(s)<=1:
return True
else:
return s[0]==s[-1] and isPal(s[1:-1])
return isPal(toChare(s))

从这个代码学到两个一个是怎么把一个字符串我们不要的东西给去掉，toChare 函数做的事情把我们想要的字符弄成一个字符串，相当于字典。

还有一个是内部函数， isPalindrome

里面又定义了两个函数，而那两个函数只能在你调用 isPa.... 里面用

递归——分而治之思想

全局变量：定义方法

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
def fibMetered(x):
global numCalls
numCalls+=1
if x==0 or x==1:
return 1
else:
return fibMetered(x-1)+fibMetered(x-2)
def testFib(n):
for i in range(n+1):
global numCalls
numCalls=0
print('fib of '+str(i)+'='+str(fibMetered(i)))
print('fib called '+str(numCalls)+'times')

全局变量使用要非常小心因为他会破坏函数的局部封装可能引起bug