Python学习笔记（四）

主题：递归

关键字：

• 递归
• 斐波那契数列(Fibonacci)的实现：递归、迭代
• 汉诺塔（Hanoi）问题

1、递归

>>> def recursion():return recursion()

函数调用自己

设置递归层数的方法：

>>> import sys
>>> sys.setrecursionlimit(10)		# 10层

例子：

# 求n!(n的阶乘)
def factorial(n):result = nfor i in range(1,n):result *= ireturn resultnumber = int(input('请输入一个正整数：'))
result_1 = factorial(number)
print('%d的阶乘是：%d' % (number,result_1))>>> ============ RESTART: E:/Python/入门练习/6.py ===========
请输入一个正整数：5
5的阶乘是：120

简化版本：

def factorial(n):if n == 1:			# 返回条件return 1else:return n * factorial(n-1)number = int(input('请输入一个正整数：'))
result = factorial(number)
print('%d的阶乘是：%d' % (number,result))

• 若输入的数字很大，会占用很大的空间，因此求阶乘时不需要用递归，循环就行。

2、斐波那契数列(Fibonacci)的实现

1	2	3	4	5	6	7	8	9	10	11	12
1	1	2	3	5	8	13	21	34	55	89	144

• 迭代实现

## 迭代实现
def fab(n):n1 = 1n2 = 1n3 = 1if n < 1:print('输入有误！')return -1while (n-2) > 0:n3 = n2 + n1n1 = n2n2 = n3n -= 1return n3
day = int(input('请输入天数：'))
result = fab(day)
if result != -1:print('总共有%d对小兔崽子诞生！' % result)

• 递归实现

## 递归实现
def fab(n):if n < 1:print("输入有误！")return -1if n==1 or n == 2:return 1else:return fab(n-1) + fab(n-2)
day = int(input('请输入天数：'))
result = fab(day)
if result != -1:print('总共有%d对小兔崽子诞生！' % result)

分解越多，消耗时间越多 -> 递归的效率低！

3、汉诺塔（Hanoi）问题

问题描述：

有A,B,C三根杆，将A针上n个从小到大叠放的盘子移动到C针，一次只能移动一个，不重复移动，小盘子必须在大盘子上面。

游戏的目标：把A杆上的盘子全部移到C杆上，并仍保持原有顺序叠好。操作过程中盘子可以置于A、B、C任一杆上。

解决：

1. 以C杆为中介，从A杆将1至n-1号盘移至B杆；
2. 将A杆中剩下的第n号盘移至C杆；
3. 以A杆为中介；从B杆将1至n-1号盘移至C杆。

知乎：

如何理解汉诺塔的递归？

def hanoi(n, x, y, z):if n==1:print(x, '-->', z)else:hanoi(n-1, x, z, y)# 将前(n-1)个盘子从x移动到y上print(x, '-->', z)  # 将x上最底层的盘子移动到z上hanoi(n-1, y, x, z)# 将y上的(n-1)个盘子移动到z上n = int(input('请输入汉诺塔的层数：'))
hanoi(n, 'X', 'Y', 'Z')

结果：

请输入汉诺塔的层数：3
X --> Z
X --> Y
Z --> Y
X --> Z
Y --> X
Y --> Z
X --> Z