一、汉诺塔的递归

汉诺塔问题一直都是经典的递归问题。

大概的思想就是将最大的圆盘移动到右边的柱子上，所以我们需要将其他的圆盘移动到中间的柱子上；

所以这个问题就变成了如何将 N-1 个圆盘移动到中间的柱子上。

思路：

• 要将 N 个圆盘从左边柱子移动到右边柱子：

1. 将 N-1 个圆盘从左边柱子移动到中间柱子。
2. 将最大的圆盘从左边柱子移动到右边柱子。
3. 将 N-1 个圆盘从中间柱子移动到右边柱子。

递归的定义：

• 链条：递归的链条比如n*(n-1)就是链条，简单的说就是循环的部分。
• 基例：存在一个或多个不需要递归的基例。

这里left => right为基例

def hanoi(height, left='left', right='right', middle='middle'):
    if height:  # 如果
        hanoi(height - 1, left, middle, right)
        print(left, '=>', right)
        hanoi(height - 1, middle, right, left)
hanoi(3)