迭代:
e.g. 计算 x*p
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)!=.....
用递归思想做乘法:
def multi(a,b): if b==1: return a else: return a+multi(a,b-1)每次调用递归都会创建一个新的环境,包含新的局部变量
当最后一次递归实现后,会一步一步代回被调用的地方
assert函数:
检查输入是否符合假设,符合则执行函数体,否则结束并报错
e.g. 斐波那契数列
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. 回文判定
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.... 里面用
递归——分而治之思想
全局变量: 定义方法
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