递归的定义:即对自己自身内容的引用。
有用的递归函数应包含以下几步份:
- 当函数直接返回值时有基本的实例(最小可能性问题);
- 递归实例,包括一个或者多个问题较小部分的递归调用;
递归的关键就是将问题分解为小部分,说白了就是递归不能无休止的执行下去,因为它总是以最小可能性问题结束。
递归实现阶乘:
阶乘的数学定义:
- 1的阶乘是1;
- 大于1的数n的阶乘就是n乘n-1的阶乘;
# -*- coding: utf-8 -*-
def factorial(n):
if n==1:
return 1
else:
return n * factorial(n-1)
number = int(input("请输入一个数:"))
print factorial(number)
递归实现整数的幂:
幂的递归设计:
- 对于任何整数x,power(x,0)是1;
- 对于任何大于0的数来说,power(x,n)是x乘以(x,n-1)的结果;
# -*- coding: utf-8 -*-
def power(x,n):
if n==0:
return 1
else:
return x*power(x,n-1)
x = int(input("请输入整数x: "))
num = int(input("请输入幂整数n:"))
print power(x,num)
递归实现费纳波切数列:
- 1,1,2,3,5,8,13,21,34,55,89,144,233,377.............(当n>3时,为前两项之和)
# -*- coding: utf-8 -*-
def sequence(n):
if n==1:
return 1
elif n==2:
return 1
else:
return sequence(n-1)+sequence(n-2)
num = int(input("请输入n:"))
print sequence(num)当n很大时,递归实现速度非常慢。
递归实现汉诺塔:
算法:当只有一个盘子的时候,只需要从将A塔上的一个盘子移到C塔上。
当A塔上有两个盘子是,先将A塔上的1号盘子(编号从上到下)移动到B塔上,再将A塔上的2号盘子移动的C塔上,最后将B塔上的小盘子移动到C塔上。
当A塔上有3个盘子时,先将A塔上编号1至2的盘子(共2个)移动到B塔上(需借助C塔),然后将A塔上的3号最大的盘子移动到C塔,最后将B塔上的两个盘子借助A塔移动到C塔上。
当A塔上有n个盘子是,先将A塔上编号1至n-1的盘子(共n-1个)移动到B塔上(借助C塔),然后将A塔上最大的n号盘子移动到C塔上,最后将B塔上的n-1个盘子借助A塔移动到C塔上。
综上所述,除了只有一个盘子时不需要借助其他塔外,其余情况均一样(只是事件的复杂程度不一样)。
# -*- coding: utf-8 -*- #该函数表示将x移到z上借助y
def hanoi(n,x,y,z):
if n == 1:
print (x,'-->',z)
else:
#将n-1个盘子从x移到y借助z
hanoi(n-1,x,z,y) #将n-1个盘子从x移到y
print (x,'-->',z)#将最后一个盘子从x移到z上
# 将n-1个盘子从y移到z借助x
hanoi(n-1,y,x,z) #将y上n-1个盘子移到z上
num = int(input("请输入层数:"))
hanoi(num,'A','B','C')