递归的定义：即对自己自身内容的引用。
有用的递归函数应包含以下几步份：
- 当函数直接返回值时有基本的实例（最小可能性问题）；
- 递归实例，包括一个或者多个问题较小部分的递归调用；
递归的关键就是将问题分解为小部分，说白了就是递归不能无休止的执行下去，因为它总是以最小可能性问题结束。
递归实现阶乘：
阶乘的数学定义：
- 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')