python 递归

递归

递归的两个特点：

• 调用自身
• 结束条件

两个递归实例：

先打印结果再调用自身

def func1(x):
  if x>0:
    print(x)
    func1(x-1)
    
func1(5)

结果：

5
4
3
2
1

先调用自身再打印结果

def func2(x):
  if x>0:
  	func2(x-1)
    print(x)
    
func2(5)

结果

1
2
3
4
5

汉诺塔（hanoi）

思考

n个盘子时：

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

# n个盘子，a、b、c三个柱子
def hanoi(n,a,b,c):
  # 盘子的数量大于0，不然就减成负数了
  if n>0:
    # 我们会通过很多步骤讲n-1个盘子经过c柱子移动到b柱子上
    hanoi(n-1,a,c,b)
    # 再将最底下的盘子n移动到c上
    print("moving form %s to %s" % (a,c))
    # 再将b柱子上的盘子经过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