第Python數(shù)據(jù)結(jié)構(gòu)之遞歸方法詳解目錄1.學(xué)習(xí)目標(biāo)2.遞歸2.1遞歸的基本概念2.2遞歸的重要性2.3遞歸三原則2.4遞歸的應(yīng)用3.遞歸示例3.1列表求和3.2漢諾塔(TowersofHanoi)問題

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

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

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

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

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

2.遞歸

2.1遞歸的基本概念

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

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

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

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

2.2遞歸的重要性

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

2.3遞歸三原則

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

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

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

2.4遞歸的應(yīng)用

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

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

3.遞歸示例

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

3.1列表求和

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

defsum_list(list_data):

result=0

foriinrange(list_data):

result+=i

returnresult

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

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

defsum_list(list_data):

iflen(num_list)==1:

returnlist_data[0]

else:

returnlist_data[0]+sum_list(list_data[1:])

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

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

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

3.2漢諾塔(TowersofHanoi)問題

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

一次只能移動一個圓盤較大圓盤不能放在較小的圓盤上

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

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

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

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

deftowersOfHanoi(number,source=1,destination=3,auxiliary=2):

ifnumber=1:

towersOfHanoi(number-1,source,auxiliary,destination)

print("Movedisk%dfromtower%dtotower%d"%(number,source,destination))

towersOfHanoi(number-1,auxiliary,destination,source)

towersOfHanoi(number=3)

程序輸出如下所示：

Movedisk1fromtower1totower3

Movedisk2fromtower1totower2

Movedisk1fromtower3totower2

Movedisk3fromtower1totower3

Move