Python 11：递归函数

在函数内部，可以调用其他函数。如果一个函数在内部调用自身，这个函数是递归函数。
举个例子计算阶乘n! = 1 * 2 * 3 * 4... * n,用fact(n)表示，可以看出：
fact(n) = n! = 1 * 2 * 3 * 4... * n = (n-1)! * n = fact(n-1) * n,所以，fact(n)可以表示为n * fact(n - 1),只有n = 1是需要特殊处理。
于是，fact(n)用递归的方式写：

def fact(n):
    if n == 1:
        return 1
    return n * fact(n - 1)

上面就是一个递归函数。

>>> fact(1)
1
>>> fact(5)
120

递归函数的优点就是定义简单，逻辑清晰。理论上，所有递归函数都可以写成循环的方式，但逻辑不如递归清晰。

练习：汉诺塔的移动可以用递归函数非常简单实现。
请编写move(n,a,b,c)函数，它接受参数n,表示3个柱子A,B,C中第1个柱子A的盘子数量，然后打印出把所有盘子从A借助B移动到C的方法：

def move(n,a,b,c):
    if n == 1:
        print(a,'-->'c)    #a上只有一个盘子
    else：
        move(n - 1,a,c,b)    #把a上n-1块移动到b
        move(1,a,b,c)    #把a上最后一块移动到c
        move(n-1,b,a,c)    #把b上最后n-1块移动到c