f(5)-->f(4)-->f(3)-->f(2)-->...f(-∞)不断地调用自身,并且参数减1.单纯地这样调用实际上并不满足递归,当然,我们的问题也不可能得以解决的哦.
回到设计程序初:我们设计程序时,这个传入参数i是我们为解决眼前问题时的规模,i-1是小一号的问题的规模.比如:我们令f(i)为某人花掉i元钱.那么f(i)在自身调用f(i-1)时相当于自己先花掉1元后,将剩下的i-1元钱给另一个人用.显然,钱不可能为负,因此总有被花光的时刻(i=0时应当终止),相应的,重复自身调用也有终止的一刻,也即是说,递归要有出口:
deff(i):ifi==0:returnf(i-1)在花钱函数中增加了一个判断,如果i=0了,就return.这就表示当一个人拿到钱的数目为0,他得上报(return)给之前调用给他的那个人,然后层层上报,报给最初的那个人.
与此同时,我们在缩减问题规模时,可能并不是像上述例程那样,什么都不做就直接i-1,而是会"花一块钱",这其实就是我们所说的递归的副作用.注意,这是我们在问题规模减小时所加的副作用,当钱用光了,层层上报时,能不能也有副作用呢答案是显然是肯定的.我喜欢把这两种副作用称之为递过去过程中的副作用和归回来过程中的副作用
上述部分说明了:
知道了什么是递归那么我们怎么来设计递归呢
下面为了更好地体会下递归并说明上述三条,将下列问题用递归方式表达
defjiecheng(n):if(n==1):return1returnn*jiecheng(n-1)顺序打印i到j(i<=j,包含j)这个问题显然可以不用递归方式来做,但是这里正是通过使用递归来体会:自己做一部分,剩下的交给别人按同样的方式来处理,然后等待处理结果,再加上自己处理的结果
defprint_i_j(i,j):if(i>j):returnprint(i)print_i_j(i+1,j)我们再看看这个递归写法:在没到达出口条件时:先打印出i,再调用小一号规模的问题.下面是调用结果:
print_i_j(1,10)#12345678910倒序打印i到j(i<=j,包含j)实际上,我只需在上述代码中调换下打印顺序即可解决该问题:
defprint_i_j(i,j):if(i>j):returnprint_i_j(i+1,j)print(i,end="")现在来分析下print(i)放在下一次调用之前和之后的情况:
倒序时,先一鼓作气走到了i>j然后返回这一轮的父函数中,此时是i=j,紧接着print(i)也就是j的值了,然后再返回他的父函数中,i=j-1,打印的也就是倒数第二个数了.
下面我们继续
这个很显然也是可以for循环进行,不过我们就是要改成递归,体会自己做一部分工作,剩下的(小一号规模的子问题)交给和自己具有相同功能的人(自我调用)来做.
下面是该问题的一个设计思考
defsum(arr):...发现我们很在在递归内部继续写,这是为什么呢原因就在于,这个arr参数是不变的.参考:找变化:变化的量往往作为参数这一点.在求和范围不断缩小时,我们需要一个参数去描述
我们需要在不变中追求统一,在变化中寻求突破(出口)(是不是很哲学♂)
defsum(arr,begin):ifbegin==len(arr)-1:returnarr[begin]returnarr[begin]+sum(arr,begin+1)在递归中,begin从0开始不断地增加,直到到达最后一个元素下标为止.
上述例子也就很好的说明了递归中的变与不变,而在变化中添加参数也是递归设计的难点,下面再来个这种例子:
例如输入:"abcd",输出"dcba"
defreverse(str,end):ifend==0:returnstr[0]returnstr[end]+reverse(str,end-1)end从str的最后一位下标开始往回,直到0
现在,各位有无对递归设计思想中的:变化中寻找重复构以成递归,重复中寻找变化以靠近出口有了更深的理解了呢
前面的递归设计中,我们可以将其统称为:求解f(N),我们自己做一部分x,其他的交给和我同样功能的人做f(N-1),直到分不了为止.换句话说,为求解f(N),我们可以先求解缩小一次规模的问题f(N-1),加之一些副作用x.如下:
f(N)=x+f(N-1)在递归中,除了上面那种缩小一点问题规模,带点副作用,再缩小...还有将问题拆分成两个子问题去分别求解的,比如:
f(N)=f(N/2)+f(N/2)+X#将问题N拆成两半,分别求解f(N/2)f(N)=f(N-1)+f(N-2)+x#为求解f(N),需要的比现在小1号的子问题f(N-1)和小2号的子问题f(N-2)f(N)=f(N/k)+f(N/k)+f(N/k)+...求第n个斐波那契数列元素斐波那契数列1,1,2,3,5,8,13,...,我们发现从第三项开始,该位置上的值等于其前面两个位置值的和
即有天然的f(n)=f(n-1)+f(n-2),当n>=3时,当要求解n时,我们只需要分别求解n-1和n-2的结果,再相加即可.
deffibo(n):ifn<=2:return1returnfibo(n-1)+fibo(n-2)print(fibo(6))这里面的出口即为n=1或者2时,他们是天然等于1的.变化的即为这个n了,不变的是求解方法:每一项等于前面两项的和.
(细心的同学可以发现,每次我们在求f(n-1)和f(n-2)时,是分别进行递归的,因此很多东西实际上是重复计算了的,而f(n-1)实际上只需要f(n-2)+(n-1)即可求得,这其实涉及到记事本方法,也是dp方法的一个重要例子,以后有机会会继续更新的~~)
两个数m,n,若m%n=0则n为两个数的最大公约数(出口)
若m%n=k(k!=0)则求n%k(变化)
defgcd(m,n):ifn==0:returnmreturngcd(n,m%n)插入排序的递归形式#插入排序的递归形式definsert_sort(arr,k):ifk==0:return;#对前n-1个元素排序insert_sort(arr,k-1)#把位置k的元素插入到前面的部分x=arr[k]index=k-1whileindex>-1andx 递归设计思路小结: 找重复: 找变化: 变化的量通常会作为参数,(循环的过程也是变化) 找出口: 变化的极限往往就是出口.(循环的中点就是出口) 文字描述:将1~N从A移动到B,C作为辅助.要求一次只能移一个,小的不能在大的下面(最下面一个为N) 按照思路小结,先尝试把问题规模缩小,找一种划分方法: 我们发现,把1~N挪到B,B和C都为空,两个位置都能放盘子,但在2~N从A挪到B时,C上面有1,根据题意小盘上面不能放大盘,因此此时2~N不能往C上放.该问题的局面与初始不同,第2点并不是原题等价缩小的规模 显然,把1~N-1从A挪到C具有相同的局面(其余两个位置随便放).把1~N-1从C挪到B需要考虑下:此时N在B上,但是他是最大的,对于在C上的1~N-1,也是A,B两个位置都能放的,由此可见,此处问题即上一个的子问题. 各位现在可以看看汉诺塔文字描述的加粗部分和上面的1,3,子问题规模性已经说明. 接下来尝试找变化,从上述加粗的子问题父问题描述我们发现,变化的其实包括有待转移盘个数N变为N-1,从哪转移到哪(fromAtoC),那好,把这些作为参数. 最后考虑出口,显然,当N=1时,直接从A移动到B即可. defhano_tower(N,src,dis,help):''':paramN:初始的N个从小到大的盘子,N是最大编号:paramsrc:原始位置:paramdis:目标位置:paramhelp:辅助位置'''ifN==1:print("移动第"+str(N)+"个盘子,从"+src+"到"+dis)returnelse:hano_tower(N-1,src,help,dis)#先把N-1个盘子挪到辅助空间print("移动第"+str(N)+"个盘子,从"+src+"到"+dis)hano_tower(N-1,help,dis,src)#先把N-1个盘子挪到辅助空间hano_tower(3,"A","B","C")#控制台输出移动第1个,从A到B移动第2个,从A到C移动第1个,从B到C移动第3个,从A到B移动第1个,从C到A移动第2个,从C到B移动第1个,从A到B二分查找的递归法等价为子问题: 变化的量,左右两边界low,high作为参数.变化中,两者靠近,当low>high时或者找到了k时即为出口 ```pythondefbinary_search(k,arr,low,high):mid=int((low+high)/2)if(low>high):return-1ifarr[mid]==k:returnmidelifarr[mid]>k:returnbinary_search(k,arr,low,mid-1)else:returnbinary_search(k,arr,mid+1,high) bin_arr=[1,2,3,5,6,7,9,11,13,16]print(binary_search(7,bin_arr,0,len(bin_arr)-1))``` 以上是一些熟悉的例子,通过一些常见的问题修改成递归形式的过程中,了解了递归设计的方法,下面是一些经典的递归设计练习 楼梯有n个台阶,一个青蛙一次可以上1,2或3阶,实现一个方法,计算该青蛙有多少种上完楼梯的方法 令f(n)为青蛙上n阶的方法数.则f(n)=f(n-1)+f(n-2)+f(n-3),当n>=3 什么意思呢假如青蛙上10阶,那么其实相当于要么站在第9阶向上走1步,要么站在第8阶向上走两步,要么在第7阶向上走3步. 进一步来说,青蛙在到达第10阶的方法数,即为到达第9阶的方法数加上到第8阶的方法数上加第7阶的方法数的和,则有子问题: 求解f(n):求解f(n-1)求解f(n-2)求解f(n-3)三者相加找变化:变化的即为台阶数n 找出口:当n=0时,青蛙不动,f(0)=0;n=1时,有1种方法,n=2时有2种方法 defgo_stairs(n):ifn==0:return0ifn==1:return1ifn==2:return2returngo_stairs(n-1)+go_stairs(n-2)+go_stairs(n-3)2.旋转数组的最小数字把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转,输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素.例如{3,4,5,1,2}是{1,2,3,4,5}的一个旋转,该数组的最小值为1.