1.學(xué)習(xí)目標(biāo)

遞歸函數(shù)是直接調(diào)用自己或通過(guò)一系列語(yǔ)句間接調(diào)用自己的函數(shù)。遞歸在程序設(shè)計(jì)有著舉足輕重的作用，在很多情況下，借助遞歸可以優(yōu)雅的解決問(wèn)題。本節(jié)主要介紹遞歸的基本概念以及如何構(gòu)建遞歸程序。

通過(guò)本節(jié)學(xué)習(xí)，應(yīng)掌握以下內(nèi)容：

理解遞歸的基本概念，了解遞歸背后蘊(yùn)含的編程思想

掌握構(gòu)建遞歸程序的方法

2.遞歸

2.1遞歸的基本概念

遞歸是一種解決問(wèn)題的方法，它將問(wèn)題不斷的分為更小的子問(wèn)題，通過(guò)處理普通的子問(wèn)題來(lái)解決問(wèn)題。遞歸函數(shù)是直接調(diào)用自己或通過(guò)一系列語(yǔ)句間接調(diào)用自己的函數(shù)。需要注意的是，遞歸函數(shù)每次調(diào)用自己時(shí)，都會(huì)將原問(wèn)題進(jìn)行簡(jiǎn)化，最終較小問(wèn)題的序列必須收斂于基本情況，解決問(wèn)題，終止遞歸。利用遞歸可以非常優(yōu)雅的解決一些復(fù)雜問(wèn)題。很多數(shù)學(xué)函數(shù)就是遞歸定義的，比如使用遞歸定義的階乘函數(shù)：

盡管這個(gè)定義是遞歸的，但它不是無(wú)限循環(huán)無(wú)法終止的。事實(shí)上，利用此函數(shù)可以非常簡(jiǎn)單的計(jì)算階乘。例如計(jì)算3!，根據(jù)定義，有3!=3(3–1)!=3(2!)，接下來(lái)我們需要解決2!，再次應(yīng)用定義 3! = 4(2!) = 3[(2)(2?1)!] = 3(2)(1!)，繼續(xù)此過(guò)程，最后我們需要計(jì)算0!，而根據(jù)定義0!=1，計(jì)算過(guò)程就結(jié)束了：

3!=3(2!)=3(2)(1!)=3(2)(1)(0!)=3(2)(1)(1)=6

可以看到，遞歸定義并非是無(wú)限循環(huán)的，因?yàn)槊看螒?yīng)用定義，程序都會(huì)將問(wèn)題分解為更簡(jiǎn)單的子問(wèn)題，在階乘函數(shù)示例中，即為計(jì)算較小數(shù)的階乘，直到計(jì)算0!，這不需要再次應(yīng)用遞歸即可求解。當(dāng)遞歸到底時(shí)，我們得到一個(gè)可以直接計(jì)算的閉合表達(dá)式，也被稱為遞歸的“基本情況”。而函數(shù)調(diào)用自身來(lái)執(zhí)行子任務(wù)時(shí)，被稱為“遞歸情況”。

2.2遞歸的重要性

遞歸函數(shù)是從數(shù)學(xué)中借鑒的一種重要的編程技術(shù)，通常使用遞歸可以極大的降低代碼量，在許多可以分解為子問(wèn)題的任務(wù)中非常有用，例如，排序、遍歷和搜索等通常可以借助遞歸方法快速的給出解決方案。

2.3遞歸三原則

和許多算法一樣，遞歸同樣有著需要遵守的重要原則，稱為遞歸三原則：

• 遞歸算法必須有基本情況
• 遞歸算法必須改變狀態(tài)并逐漸收斂于基本情況
• 遞歸算法必須包含遞歸情況，能夠遞歸的調(diào)用自身

需要注意的是，遞歸的核心思想并不是循環(huán)，而是將問(wèn)題分解成更小、更容易解決的子問(wèn)題。

2.4遞歸的應(yīng)用

遞歸在程序設(shè)計(jì)中有著十分重要的作用，以下是一些常用到遞歸的實(shí)際場(chǎng)景：

• 斐波那契數(shù)列、階乘計(jì)算等數(shù)學(xué)問(wèn)題
• 歸并排序、快速排序
• 二分查找
• 樹和圖的遍歷以及相關(guān)問(wèn)題
• 漢諾塔

3.遞歸示例

本節(jié)中，我們將從簡(jiǎn)單的列表求和問(wèn)題入手，了解遞歸算法的使用方式，然后再了解如何解決經(jīng)典遞歸問(wèn)題——漢諾塔。

3.1列表求和

列表求和是十分簡(jiǎn)單的問(wèn)題，用來(lái)了解遞歸算法的思想再合適不過(guò)了。例如我們需要計(jì)算列表 [1, 2, 3, 4, 5] 的和，如果利用循環(huán)函數(shù)計(jì)算，則可以編寫如下代碼計(jì)算列表中所有數(shù)之和：

def sum_list(list_data):
    result = 0
    for i in range(list_data):
        result += i
    return result

如果不使用循環(huán)，我們?cè)撊绾谓鉀Q這一問(wèn)題呢？我們可以寫出求和過(guò)程((((1+2)+3)+4)+5)，而根據(jù)加法交換律，計(jì)算過(guò)程也可以寫為(1+(2+(3+(4+5))))，這時(shí)我們就可以很清楚的看到，列表的數(shù)據(jù)總和等于列表第一個(gè)元素加上其余元素：

使用 python 實(shí)現(xiàn)以上等式如下：

def sum_list(list_data):
    if len(num_list) == 1:
        return list_data[0]
    else:
        return list_data[0] + sum_list(list_data[1:])

在代碼中，首先給出了函數(shù)退出的條件，這就是遞歸函數(shù)的基本情況，在示例中就是說(shuō)，長(zhǎng)度為 1 的列表，其元素和就是列表中的數(shù)。不滿足退出條件，sum_list 則會(huì)調(diào)用自己，這就是遞歸函數(shù)的遞歸情況，也是其稱為遞歸函數(shù)的原因。

在下圖(a)中，可以看到求解 [1, 2, 3, 4, 5] 時(shí)的遞歸調(diào)用過(guò)程，每次遞歸調(diào)用都是在解決一個(gè)更接近基本情況的問(wèn)題，直到問(wèn)題不能被進(jìn)一步簡(jiǎn)化。

當(dāng)問(wèn)題無(wú)法簡(jiǎn)化時(shí)，開始拼接所有子問(wèn)題的解，下圖(b)展示遞歸函數(shù) sum_list 在返回一系列調(diào)用結(jié)果時(shí)所進(jìn)行的加法操作，當(dāng)返回到頂層時(shí)，就解決了最初的問(wèn)題。

3.2漢諾塔(Towers of Hanoi)問(wèn)題

漢諾塔(Towers of Hanoi)是一道十分經(jīng)典的謎題。它由三個(gè)塔和許多不同尺寸的圓盤組成，這些圓盤可以移動(dòng)到任何桿上。開始時(shí)圓盤按尺寸升序排列在一個(gè)塔上，頂部的圓盤最小，底部圓盤最大。謎題的目標(biāo)是將疊好的圓盤移動(dòng)到另一個(gè)桿，且滿足以下規(guī)則：

• 一次只能移動(dòng)一個(gè)圓盤
• 較大圓盤不能放在較小的圓盤上

接下來(lái)我們講解如何借助一根中間塔 Auxiliary，將高度為 n 的一疊圓盤從起始塔 Source 移到終點(diǎn)塔 Destination：

• 借助終點(diǎn)塔 Destination，將頂部的 n - 1 個(gè)圓盤從 Source 移動(dòng)到 Auxiliary
• 將第 n 個(gè)圓盤從 Source 塔移動(dòng)到終點(diǎn)塔 Destination
• 借助 Source 塔，將 n - 1 個(gè)磁盤從輔助塔 Auxiliary 移動(dòng)到終點(diǎn)塔 Destination

只要遵循漢諾塔的移動(dòng)規(guī)則，就可以遞歸地執(zhí)行上述步驟。最簡(jiǎn)單的漢諾塔是只有一個(gè)盤子，在這種情況下，只需將這個(gè)盤子移到終點(diǎn)柱子 Destination 即可，這就是基本情況。上述遞歸步驟通過(guò)逐漸減小高度 n 來(lái)向基本情況靠近，如下圖所示：

算法的關(guān)鍵在于進(jìn)行兩次遞歸調(diào)用，第一次遞歸是將除了最后一個(gè)圓盤以外的其他所有圓盤從 Source 塔移到輔助塔 Auxiliary 。然后將最后一個(gè)圓盤移到終點(diǎn)塔 Destination。第二次遞歸是將圓盤從 Auxiliary 移到 Destination：

def towersOfHanoi(number, source=1, destination=3, auxiliary=2):
    if number >= 1:
        towersOfHanoi (number - 1, source, auxiliary, destination)
        print("Move disk %d from tower %d to tower %d" % (number, source, destination))
        towersOfHanoi (number - 1, auxiliary, destination, source)
towersOfHanoi(number=3)

程序輸出如下所示：

Move disk 1 from tower 1 to tower 3
Move disk 2 from tower 1 to tower 2
Move disk 1 from tower 3 to tower 2
Move disk 3 from tower 1 to tower 3
Move disk 1 from tower 2 to tower 1
Move disk 2 from tower 2 to tower 3
Move disk 1 from tower 1 to tower 3