在算法的實(shí)現(xiàn)中，遍歷與遞歸是經(jīng)常出現(xiàn)的兩種操作。遍歷其實(shí)就是使用一個(gè)for循環(huán)來遍歷集合里的元素，在編程中經(jīng)常出現(xiàn)，通俗易懂，至于遞歸，我們先來看看遞歸的概念：在數(shù)學(xué)與計(jì)算機(jī)科學(xué)中，是指在函數(shù)的定義中使用函數(shù)自身的方法。其實(shí)遞歸在程序語言中簡單的理解就是方法自己調(diào)用自己。遞歸其實(shí)和循環(huán)是非常像的，循環(huán)都可以改寫成遞歸，遞歸未必能改寫成循環(huán)，這是一個(gè)充分不必要的條件。今天這篇文章就帶大家深入解析遞歸算法。

遞歸做為一種算法在程序設(shè)計(jì)語言中廣泛應(yīng)用。一個(gè)過程或函數(shù)在其定義或說明中有直接或間接調(diào)用自身的一種方法，它通常把一個(gè)大型復(fù)雜的問題層層轉(zhuǎn)化為一個(gè)與原問題相似的規(guī)模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對(duì)象的無限集合。一般來說，遞歸需要有邊界條件、遞歸前進(jìn)段和遞歸返回段。當(dāng)邊界條件不滿足時(shí)，遞歸前進(jìn)；當(dāng)邊界條件滿足時(shí)，遞歸返回。

構(gòu)成遞歸需具備的條件：

1. 子問題須與原始問題為同樣的事，且更為簡單；

2. 不能無限制地調(diào)用本身，須有個(gè)出口，化簡為非遞歸狀況處理。

通過使用遞歸，可以把一個(gè)大型復(fù)雜的問題逐層轉(zhuǎn)化為一個(gè)與原問題相似的規(guī)模較小的問題來求解。因此如果使用遞歸，可以達(dá)到使用少量的代碼就可描述出解題過程所需的多次重復(fù)計(jì)算的目的，減少了程序的代碼量 。

下面用一個(gè)例子來具體感受一下遞歸操作：

大家應(yīng)該都比較熟悉階乘的算法：3！= 3 * 2 * 1 ； 4！= 4 * 3 * 2 * 1

不難看出，在這里反復(fù)執(zhí)行了一個(gè)逐漸-1和相乘的操作，如果可以使用某段代碼達(dá)到重復(fù)調(diào)用的效果就很方便了，在這里就可以使用遞歸：

func factorial(_ n:Int) -> Int{

    return n < 2 ? 1: n * factorial(n-1)

}

factorial(3) //6

在上面的代碼里，factorial函數(shù)調(diào)用了它自己，并且在n<2的時(shí)候返回了1；否則繼續(xù)調(diào)用自己。從代碼本身其實(shí)不難理解函數(shù)調(diào)用的方式，但是這個(gè)6究竟是怎么算出來的呢？這就涉及到遞歸的實(shí)現(xiàn)原理了。

遞歸的調(diào)用實(shí)際上是通過調(diào)用棧（callback stack）來實(shí)現(xiàn)的，為了加深我們的理解可結(jié)合下圖來看：

由上圖可以看出，整個(gè)遞歸的過程和棧的入棧出棧的操作非常類似：橘黃色背景的圓角矩形代表了棧頂元素，也就是正在執(zhí)行的操作，而灰色背景的圓角矩形則代表了其余的元素，它們的順序就是當(dāng)初被調(diào)用的順序，而且在內(nèi)容上保持了當(dāng)時(shí)被調(diào)用時(shí)執(zhí)行的代碼。

現(xiàn)在我們按照時(shí)間順序從左到右來說明一下整個(gè)調(diào)用的過程：

最開始傳入3之后，3滿足了n>=2的條件，繼續(xù)調(diào)用自己：3 * factorial(2) ，入棧。

傳入2之后，2滿足了n>=2的條件，繼續(xù)調(diào)用自己：2 * factorial(1) ，入棧。

傳入1之后，1滿足了n<2的條件，停止調(diào)用自己，返回了1，出棧。

此時(shí)的棧頂元素為2 * factorial(1) ，而剛剛factorial(1)返回了1，所以現(xiàn)在這里變成了2 * 1 = 2，出棧。

同樣地，此時(shí)棧頂元素為3 * factorial(2)里的 factorial(2)返回了2，所以現(xiàn)在這里變成了3 * 2 = 6，出棧。

最后，factorial(3)返回了6，出棧，遞歸結(jié)束。

整個(gè)遞歸的過程可以大致理解為：在使遞歸繼續(xù)的條件為false之前，持續(xù)遞歸調(diào)用，以棧的形式保存調(diào)用上下文（臨時(shí)變量，函數(shù)等）。一旦這個(gè)條件變?yōu)閠rue，則立即按照出棧的順序（入棧順序的逆序）來返回值，逐個(gè)傳遞，最終傳遞到最開始調(diào)用的那一層返回最終結(jié)果。再簡單點(diǎn)，遞歸中的“遞”就是入棧，傳遞調(diào)用信息；“歸”就是出棧，輸出返回值。

而這個(gè)分界線就是遞歸的終止條件。很顯然，這個(gè)終止條件在整個(gè)遞歸過程中起著舉足輕重的作用。試想一下，如果這個(gè)條件永遠(yuǎn)不會(huì)改變，那么就會(huì)一直入棧，就會(huì)發(fā)生棧溢出的情況。事實(shí)上，遞歸算法解題相對(duì)常用的算法如普通循環(huán)等，運(yùn)行效率較低。因此，在有選擇的情況下不建議使用遞歸算法。到這里關(guān)于深入解析遞歸算法的所有問題，就講完了，希望大家對(duì)于遞歸的知識(shí)有所掌握和了解，如果對(duì)遞歸相關(guān)的知識(shí)還有其它問題，我們可以在本站的數(shù)據(jù)結(jié)構(gòu)和算法教程中學(xué)習(xí)更多的優(yōu)秀算法，讓我們?cè)诮忸}有更多的選擇。