算法基础之递归算法

'''递归，在一个函数内部调用自身本身，就叫做递归函数,<br />递归的主要思想就是把现在要做的事情放到上一个事情，依次类推，最终得到自己想要的结果，就如著名的汉诺塔问题，用递归函数可以很方便的解答'''<br />'''汉诺塔问题：有a，b，c三根主子，n个盘子，从下往上按照大小顺序摞着n个盘子，每次只能移动一个盘子，而且大盘子不能放在小盘子上面，<br />问总共要移动多少次才能将盘子全部从a移到c，并打印出移动顺序'''<br />'''思路：每一次都是先将a盘的n-1个盘子放到b盘，再将a盘的最后一个盘子放入c盘，关于步骤，将n-1个盘子借c盘从a盘移到b盘后，<br />再把第n个从a盘移到c盘，最后再借c盘把n-2个盘子从b盘移到a盘，再将第n-1个盘子从b盘移到c盘'''<br />def move(n,a,b,c):<br />#a是初始盘，b是中间盘，c是目标盘<br />    if n==1:<br />        print (a,'-->',c)<br />    else:<br />        move(n-1,a,c,b)<br />        print(a,'-->',c)<br />        move(n-1,b,a,c)<br />print(move(3,'A','B','C'))<br />''''''<br />'''-------递归问题拓展-------'''<br />'''Fibonacci问题：这个问题是：有小兔一对，若第二个月它们成年，第三个月生下小兔一对，以后每月生产一对小兔，而所生小兔亦在第二个月成年，<br />第三个月生产另一对小兔，以后亦每月生产小兔一对，假定每产一对小兔必为一雌一雄，且均无死亡，试问一年后共有小兔几对？'''<br />'''思路：第一个月有一对小兔子，第二个月后这对兔子成年了，第三个月生产了一对兔子，第四个月后原来的兔子又生产了一对兔子，<br />而第三个月生产的小兔子成年了...依次类推，可以知道，主要是由两种兔子，一种是还未成年的兔子，第二种是已经成年的兔子，<br />而已经成年的兔子会每个月都生产一对兔子，未成年的兔子会在下个月生产一对兔子，设第一个月有n对兔子，<br />则第n个月的兔子数量会等于第n-1个月的兔子数量加上第n-1个月的兔子生产的兔子数量（即第n-1个月的未成年兔子数量)，所以可以总结出这个月的未成年兔子数量等于上个月的兔子总数，<br />可列出方程f(n)=f(n-1)+f(n-2)'''<br />def rab(n):<br />    if n==1 or n==2:<br />        return 1<br />    elif n>2:  #这里的判断条件不能少...如果是不加则可能一直到负数...<br />        return rab(n-1) + rab(n-2)<br />    elif n<=0:<br />        return ('输出错误')<br />print (rab(10))