递归的特性

• 调用自身
• 有终止条件

汉诺塔问题

三根柱子ABC，n个盘子要从A移动到C

• 从上到下的n-1个盘子从A经过C移动到B
• 第n个盘子从A移动到C
• B柱上的n-1个盘子经过A移动到C

def hanoi(n,a,b,c): #n个盘子从a，经过b，移动到c
    if n > 0:
        hanoi(n-1,a,c,b) #n-1个盘子从a，经过c，移动到b
        print('从%s移动到%s' % (a,c)) #第n个盘子，从a移动到c，只要一步
        hanoi(n-1,b,a,c) #n-1个盘子从b，经过a，移动到c

汉诺塔移动n个盘子所需次数公式：hanoi(n) = 2hanoi(n-1) + 1 约2^n
汉诺塔问题满足递归的特性，调用自身，终止条件是n>0