我們在前面學習過遞歸函數，遞歸函數采用的就是遞歸算法，前面我們通過最常見的菲波那切數列去學習了遞歸函數，這一節(jié)我們再來詳細了解一下遞歸算法。

1. 遞歸算法

        遞歸算法（英語：recursion algorithm）在計算機科學中是指一種通過重復將問題分解為同類的子問題而解決問題的方法。遞歸式方法可以被用于解決很多的計算機科學問題，因此它是計算機科學中十分重要的一個概念，遞歸算法有三個特點：

        1) 遞歸的過程一般通過函數或者子過程來實現。

        2) 遞歸算法在它內部來直接或者間接的調用自身的算法。

        3) 遞歸算法就是把規(guī)模大的問題轉換為規(guī)模小的問題，然后遞歸調用函數來求解的過程。

        遞歸算法也有幾點需要注意的事項，在前面遞歸函數中我們也提到過，分別是：

        1) 遞歸是在函數本身調用函數本身。

        2) 遞歸的效率比較低，如果有時間限制不建議使用。

        3) 遞歸過程中需要有一個明確的結束條件，即遞歸出口。

2. 漢諾塔問題

        漢諾塔問題也是一道十分經典的算法題目。

        問題描述如下：

        漢諾塔是一種古老的游戲。

        一共3個柱子，標號為1,2,3。

        1號柱子有從大到小一共n個盤子。

        每次移動最上方的一個盤子，可以移動到其他的柱子。

        任何一個盤子，都不能疊在比它更小的盤子的上方。

        請把盤子從1號柱子，全部移動到3號柱子。

        起始：

        移動到這樣：

        現在，給出了n個盤子，請你描述一下用最短次數移動的過程。

        我們先來分析這種三個盤子的時候的移動方式為：

 ->

->

->

->

        代碼如下：

  i = 1
def move(n,fr,to):
    global i
    print('這是第%d步:把%d號盤子從%s移動到%s'%(i,n,fr,to))
    i += 1
def hanoi(n,a,b,c):
    if n == 1:
        move(1,a,c)
    else:
        hanoi(n-1,a,c,b)
        move(n,a,c)
        hanoi(n-1,b,a,c)
if __name__ == '__main__':
    n = int(input('輸入A上面盤子的數量:'))
    print('移動開始')
    hanoi(n,'A','B','C')

        我們輸入3來測試一下移動步驟與上圖是否對應：

輸入A上面盤子的數量:3
移動開始
這是第1步:把1號盤子從A移動到C
這是第2步:把2號盤子從A移動到B
這是第3步:把1號盤子從C移動到B
這是第4步:把3號盤子從A移動到C
這是第5步:把1號盤子從B移動到A
這是第6步:把2號盤子從B移動到C
這是第7步:把1號盤子從A移動到C

        通過結果我們可以看到和圖中所示一致，注意代碼中的hanoi(n,a,b,c)表示為把A根柱子上的n個盤子通過B柱子移動到C柱子上，hanoi(n-1,1,3,2)然后就要執(zhí)行hanoi(n-1,2,1,3)，主要是通過這個遞歸函數來完成柱子的移動。

3. 總結

        遞歸思想在我們的學習中經常會用到，如何巧妙的運用遞歸，可以參考一下前面遞歸函數中的內容。