递归算法
递归（Recursion）是一种很特殊的算法，其定义是：加入一个函数或子程序是由自身所定义或调用的，就称为递归。递归至少需要两个条件：
- 可以反复执行的递归过程
- 一个跳出执行过程的出口
比如数学上的阶乘函数，可以看做是典型的递归范例，一般以！来代表阶乘。例如4的阶乘就是4！
4！= 4 x 3 x 2 x 1
4! = (4 * 3!)---->(4 * 3 * 2!) ------>(4 * 3 * 2 * 1)
函数算法表示是
def factorial(i): if i == 0: return 1 else: ans = i * factorial(i - 1) #反复执行递归过程
使用for循环设计一个计算0！~ n!的递归程序
sum = 1n = int(input('请输入n=''))for i in range (0,n+1): for j in range(i ,0,-1): sum *= j print('%d != %3d' % (i,sum)) sum = 1
递归算法又可以分为直接递归和间接递归：
-
直接递归（Direct Recursion）：在递归函数中允许直接调用该函数自身
def Fun(...): .......if ....: Fun(...) ...... -
简介递归（Indirect Recursion）：在递归函数中调用其他递归函数，再从其他递归函数调用回原来的递归函数
def Fun1(...): ......if ......: Fun2(...) ....... def Fun2(...): ......if ......: Fun1(...) ......
斐波拉契数列
| 0 | n=0 | |
|---|---|---|
| Fn | 1 | n=1 |
| Fn-1 + Fn-2 | n=2,3,4,5,…(n为正整数) |
简单来说，这就是一个数列的第零项是0，第一项是1，这个数列其他后续项的值是前两项的数值之和。
def fib(n): if n == 0: return 0 elif n == 1 or n == 2: return 1 else: #否则返回fib(n-1) + fib(n-2) return (fib(n-1) + fib(n-2))
例子：设计一个计算第n项斐波拉契数列的递归程序：
def fib(n): if n == 0: return 0 elif n == 1 or n == 2: return 1 else: return (fib(n - 1) + fib(n - 2)) n = int ( input ("请输入n="))for i in range(n + 1): print('fib(%d) = %d' % (i,fib(i)))
汉诺塔问题
汉诺塔问题也是很典型的递归方式和堆栈来解决，因为它满足递归的两大特性：①有反复执行的过程②有停止的出口
汉诺塔的游戏规则就是把一定数量的盘子每次移动一个，全部从第一个桩移动到第三个桩上，在移动的过程中要保证大盘子在下面
借助递归的思想，加入有n个盘子，我们可以将n个盘子看做两个组成结构，就是n-1个盘子和一个盘子，每次都是将n-1个盘子移动到第二个桩上，将一个盘子（最大的）移动到第三个桩上，然后将第二个桩变换为第一个桩，继续将剩下的n-1个盘子分为两个结构进行移动，直到不能分为止
移动步骤：
- 将n-1个盘子从木桩1移动到木桩2
- 将第n个最大的盘子从木桩1移动到木桩3
- 将n-1个盘子从木桩2移动到木桩3
- 就是把木桩2当做是木桩1逐次分解进行迭代
算法实现：
"""
n:需要移动的盘子数量
p1,p2,p3:三根木桩
"""
def hanoi(n,p1,p2,p3):
if n == 1:
print("盘子从%d移动到了%d"%(p1,p3))
else:
hanoi(n-1,p1,p3,p2)
print("盘子从%d移动到%d"%(p1,p3))
hanoi(n-1,p2,p1,p3)
j = int(input("请输入要移动盘子的数量："))
hanoi(j,1,2,3)