Py008-01-02递归和汉诺塔

递归

特点

  • 调用自身
  • 结束条件
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def fn1(x):
    print(x)
    fn1(x-1)


def fn2(x):
    if x>0:
        print(x)
        fn2(x+1)

# 合法递归   fn3(3)  ==>3 2 1
def fn3(x):
    if x>0:
        print(x)
        fn3(x-1)

# 合法递归   fn4(3)  ==>1 2 3
def fn4(x):
    if x>0:
        fn4(x-1)
        print(x)

汉诺塔问题

  • 三个柱子 A B C
  • A上有3个盘子 大盘子在最下 小盘子在最上
  • 只能在 三个柱子上移动
  • 实现 把A上的盘子移动到C
1
2
3
4
5
6
7
8
9
10
n=2时
1. 把小圆盘从A移动到B
2. 把小圆盘从A移动到C
3. 把小圆盘从B移动到C


n=n时
1. 把n-1个盘子从A经过C移动到B
2. 把第n个圆盘从A移动到C
3. 把n-1个圆盘从B经过A移动到C

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
'''
a:从那个盘子
b:经过那个盘子
c:到那个盘子
'''
def hanoi(n,a,b,c):
    if n>0:
        hanoi(n-1,a,c,b)
        print('moving from %s to %s'%(a,c))
        hanoi(n-1,b,a,c)


hanoi(3,'A','B','C')

'''
moving from A to C
moving from A to B
moving from C to B
moving from A to C
moving from B to A
moving from B to C
moving from A to C
'''

汉诺塔移动次数的递推式：h(x)=2h(x-1)+1
h(64)=18446744073709551615

假设每秒搬一个盘子，则需要5800亿年！