階乘

舉個(gè)例子，我們來(lái)計(jì)算階乘 n! = 1 * 2 * 3 * ... * n，用函數(shù) fact(n)表示，可以看出：
fact(n) = n! = 1 * 2 * 3 * ... * (n-1) * n = (n-1)! * n = fact(n-1) * n
于是，fact(n)用遞歸的方式寫(xiě)出來(lái)就是：

def fact(n):

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

如果我們計(jì)算fact(5)，可以根據(jù)函數(shù)定義看到計(jì)算過(guò)程如下

image.png

漢諾塔問(wèn)題

我們對(duì)柱子編號(hào)為a, b, c，將所有圓盤(pán)從a移到c可以描述為：
如果a只有一個(gè)圓盤(pán)，可以直接移動(dòng)到c；
如果a有N個(gè)圓盤(pán)，可以看成a有1個(gè)圓盤(pán)（底盤(pán)） + (N-1)個(gè)圓盤(pán)，首先需要把 (N-1) 個(gè)圓盤(pán)移動(dòng)到 b，然后，將 a的最后一個(gè)圓盤(pán)移動(dòng)到c，再將b的(N-1)個(gè)圓盤(pán)移動(dòng)到c。
請(qǐng)編寫(xiě)一個(gè)函數(shù)，給定輸入 n, a, b, c，打印出移動(dòng)的步驟：
move(n, a, b, c)
例如，輸入 move(2, 'A', 'B', 'C')，打印出：
A --> B
A --> C
B --> C

def move(n,a,b,c):

 if n==1:

        print (a,'-->',c) #這其實(shí)是只有一個(gè)圓盤(pán)需要從A到C的情況。所有遞歸，最終都是走到這一步。

        return #這是結(jié)束遞歸，省略了None。沒(méi)有這句的話，遞歸沒(méi)辦法結(jié)束。

 move(n-1,a,c,b) #將A柱的n-1個(gè)盤(pán)移到B柱，這里毫無(wú)爭(zhēng)議。注意形參順序變化了。

 print a,'-->',c #這句話才是第一個(gè)柱子的第n個(gè)圓盤(pán)移動(dòng)到目標(biāo)柱子。

 move(n-1,b,a,c))#過(guò)渡柱子B上（n-1）個(gè)圓盤(pán)B遞歸移動(dòng)到目標(biāo)柱子C