Excel星球

Excel星球

微信號 AhaExcel

功能介紹 建議常用Excel的職場人關注，海量教程隨學隨用，隨用隨查。 主創(chuàng)：看見星光，微軟全球最有價值專家、Excel圖書作者、培訓師。 內容：每日四文，一篇函數(shù)教程、一篇VBA教程、一個短視頻小技巧、一篇雜文。

以下文章來源于VBA編程學習與實踐 ，作者qee用

風吹衣袖  月上西樓   昨夜的夢中……

HI，我是星光，聽說有人覺得最近公眾號分享的內容比較簡單，所以，從論壇里搬來 qee用 大神的原創(chuàng)神貼……來吧，了解下什么是遞歸▼

……

0．先禮后兵（代前言）

禮者，理也；兵者，實戰(zhàn)也。本文以此來循序探討遞歸，卻未必是漸進的，盡管我盡力想做到，如果你看到了無法理解的某些詞句，可以先跳過去，作者鼓勵你把它做為關鍵詞在IE上搜索，以使這些概念更清晰和全面。本文大體上從遞歸的一般理論到相關知識。但既謂之漫談，也不拘泥于此。

我們開始吧。

1．何謂遞歸？

通?？吹降亩x是：當過程（函數(shù)）（本文后面將省略上面括號里的內容）直接或間接調用了自己時，則發(fā)生了遞歸。

直接：入口àAà入口

間接：入口àAàBà入口

請原諒我無法用文字把上面的圖畫得象環(huán)型那樣直觀，第一個是直接調用，即過程A調用了自身，第二個是間接調用，即過程A調用了B，B又調用了A自身。

令：C為AàB，則上面的間接調用模式變?yōu)?/span>

入口àCà入口

這其實就是直接調用的模式?？梢哉J為，C之所以被分解為兩個過程A和B，只是程序為了在步驟上更清晰而已（我們通常不都是這樣寫代碼嗎）！筆者首先想告訴你的，不要去節(jié)外生枝地管什么直接間接而生澀地記住一個看似周全的定義，本人對“概念”的一貫態(tài)度是，能夠識別即可， 遞歸就是指過程自己調用自己！

2．遞歸是算法嗎？

就算是吧。反正大家都這么叫了，存在即合理嘛。程序=數(shù)據(jù)結構+算法，它總不會是數(shù)據(jù)結構吧。

如同所有的事物一樣，算法從不同的角度也可以有不同的分類，這種從不同角度進行的分類往往并不是排斥的，清楚這一點，可以使你賞到各種算法的稱謂時不會因迷茫而人云亦云。算法分類按照處理的任務，有我們常說的排序算法、查找算法；按照指導思想，有分而治之算法、窮舉算法。而所謂遞歸算法，是指在過程中使用了“自己調用自己”的算法，它是按什么分類的呢？留下這個問題，在后面慢慢體會吧，呵呵。

3．遞歸是必需掌握的嗎？

不然！程序結構的三元素是順序、選擇、循環(huán)，用這三種結構可以完成任何功能的代碼。不用我多說吧，所有的程序設計教科書都是這樣說的，很多早期的語言甚至不支持遞歸。讓我們回頭看一下前面的遞歸模式，它是不是和“循環(huán)”結構很象？是的，所有可用遞歸完成的代碼也都可以用循環(huán)來完成，反之亦然。二者的轉換方法我們會在后面探討。

4．遞歸的效率問題

搜一下網(wǎng)絡資源，說什么的都有，一時本人也沒了主章。這個問題的結論留到本文的最后來下。

先說下我的觀點：因為遞歸過程中，存在著大量的進退棧操作，這種進退棧會吃掉大量的系統(tǒng)資源，同時很多是無謂的操作，因此無論是資源還是時間的效率都比等價的循環(huán)要低。以菲波利數(shù)列為例，遞歸的時間復雜度是O(nlogn)，循環(huán)是O(n)，顯然，當n>2時，即有nlogn>n。在遞歸技術早期，編譯系統(tǒng)是把整個過程都壓棧的，隨著這項技術逐步研究深入，只需要對局部變量做棧處理，相對有了很大優(yōu)化。但，總體上效率低的結論不會變。

也許你已經(jīng)在質疑了：遞歸已經(jīng)被你說得一無是處，又那么生澀難懂，還有必要學它嗎？！不然，它實在很有用，適用于它的舞臺容后道來。

5．遞歸難嗎？

難者不會，會者不難。

嘿嘿，等于沒說。客觀地說，初次接觸遞歸對大多數(shù)人，都會有一個從難到易的適應過程。甚至看過并且“理解”了一些遞歸的代碼，仍不敢言易，原因何在呢？

來看一個用遞歸求解迷宮的思路，迷宮有一個入口和一個出口，從入口進入后，如果遇到了分支，則每一個分支又相當于一個入口…這樣就形成了一個遞歸，由此解題的思路是從入口處派入一支尋路的隊伍，當遇到分支時，支隊長把這個隊伍分成若干個小分隊，如此下去，總會有一支分隊找到出口，然后再逐級報告它的上一級，這樣便會得出迷宮的行走路線。在這里，尋路的開始階段你不會知道需要一支由多少人組成的尋路隊伍，遞歸就是這樣！它假定你有足夠的資源來支付未知不確定的帳單。這和我們正常的思維是不同的，程序是我們讓計算機執(zhí)行我們意圖的語言指令，但在日產(chǎn)生活中，我們有使用遞歸思想讓自己或別人去做事的習慣嗎？現(xiàn)實中如果真的遇到了迷宮問題，有人會這樣做嗎？

另一方面，我們需要知道我們的思路和代碼是否正確，為什么正確？這就是正確性的證明問題，但遺憾的是，人的思維深度是有限的，兩層或三層的遞歸也許在你的大腦中可以想象出它的完整過程，更多層以后，遞歸正確性的證明只能使用抽象的方法，但我們通常缺少這種訓練。

回到前面的迷宮問題，仔細地看看（想想）遞歸的思路，你會發(fā)現(xiàn)，如果資源能夠得到保證的話，這種思路確實使問題變得簡單了！而且一旦你形成了這種思維習慣，你會發(fā)現(xiàn)原本很多復雜的問題都變得如此簡單！

到這兒，如果你突然覺得遞歸簡單了，那我也不得不告訴你，別高興得太早，學會一門技術不會這么簡單。

6．神奇的“黑匣子”

從現(xiàn)在起，稍稍放慢一下閱讀的速度，呵呵。

“黑匣子”是一種抽象的程序設計思想，是面象對象的程序設計思想之一，但事實上，這種思想在面象對象的程序設計理論提出之前早已被廣泛應用。它在邏輯上把一個復雜的任務劃分為若干相對簡單的子任務，然后把子任務當成是“黑匣子”來考慮，即調用程序中只需要為子程序（任務）起一個可以識別的名子（然后通過這個名子進行調用）、需要傳遞的參數(shù)，然后坐享應該得到的結果，而不再去考慮子任務的內部實現(xiàn)細節(jié)（對子任務的實現(xiàn)另行獨立考慮）。這樣的結果是使程序結構更清晰，可讀性也更強（這對復雜的任務非常重要）。這樣，我們只需要要知道，當使用下句代碼時：

MySubNamen

我們可以確信得到期望的運行結果，而不必去想MySubName的運行過程，這就是“黑匣子”的神奇。這一思想對理解遞歸至關重要，因為在遞歸中，MySubName同時也是調用程序自己的名子。

如果您覺得還有不清楚，不要緊，在稍后的實例中還會作出解釋。

7．第一個經(jīng)典：階乘

所以說經(jīng)典，是因為幾乎所有介紹遞歸的文章都會提到它，也許階乘是我們能想到的最簡明的事例。先來看一下常規(guī)思路（循環(huán)）的算法程序：

Function Nx1(n)   Dim i%   Nx1 = 1   For i = 1 To n     Nx1 = Nx1 * i   Next i End Function

再來看一下用遞歸的寫法：

函數(shù)名：Nx2，參數(shù)：n，功能：返回n的階乘。

Function Nx2(n)   If n = 1 Then Nx2 = 1: Exit Function   Nx2 = n * Nx2(n - 1) End Function

第二句代碼的含義是n的階乘等于n乘以n-1的階乘，別忘了我們說過的“黑匣子”—這里既是Nx2！所以不要去想Nx2(n-1)是怎么樣的計算過程啦。經(jīng)典吧哈？這段代碼的經(jīng)典還在于：它包含了一般遞歸程序的所有要素。來描述一下：

（1）遞歸程序至少要有一個出口條件，已使得程序能夠停止下來。這個出口條件又被稱為“基狀態(tài)”，在“基狀態(tài)”下，結果可以直接被表述。如上例的第一句“Ifn=1ThenNx2=1:ExitFunction”。

（2）遞歸程序要有遞歸部分，我們設參數(shù)n通常表示問題的復雜度，n=1表示“基狀態(tài)”，遞歸部分需要完成的是：

a．將復雜度為n的問題轉化為低復雜度n-1，使它向復雜度為1的“基狀態(tài)”問題逼近。

b．完成上述轉換中n層和n-1層的銜接處理。這種銜接可以是數(shù)學關系，如本例“n*”，也可以不是。

程序員要做的就是將可用遞歸解決的問題按照上述邏輯部分歸納出來，這需要在實戰(zhàn)中增長經(jīng)驗。對初次接觸的朋友需要補充的是，上面兩部分劃分只是抽象的表述，這意味著實際遞歸問題的復雜度通常不是用一個參數(shù)表示，“基狀態(tài)”也可以不是數(shù)字1，低復雜度n-1的參數(shù)不是比低復雜度n的參數(shù)小，甚至不是數(shù)字關系。

（3）由于大多數(shù)遞歸程序是使用參數(shù)來描述復雜度，并且在遞歸部分需要降低復雜度，所以一般情況下，遞歸程序是作為子程序被調用，而不能獨立運行。在調用遞歸程序的程序中需要初始化復雜度參數(shù)，即所謂“種子”。

我不排除你可以構思出一些不使用參數(shù)并且可以自啟動的遞歸程序，但那只屬于例外，而且也違背遞歸的本意。

（4）遞歸程序與循環(huán)程序相比，顯得簡潔，正如你所看到的。而且你一旦熟悉了這種模式，它更易讀，這在復雜的問題上會表現(xiàn)地更明顯。

本節(jié)的最后，也不得不說說，對這個經(jīng)典程序的有關批評的聲音，因為階乘的定義從來就是：n!=1ⅹ2ⅹ…ⅹn。所以使用循環(huán)的方法更容易被理解和接受，而且也說不上繁瑣！算法是為了實用的，而不是為了“經(jīng)典”，在這里我們沒有看到使用遞歸的任何必要性和優(yōu)勢，很多通過這個實例接觸遞歸的人從此形成了對遞歸根深蒂固的評價：一個花架子而已！并永遠忽略了遞歸。這就是很多高手不研究遞歸的原因吧。下一個經(jīng)典將改變您的這種認識。

8．第二個經(jīng)典：漢諾塔

也許您已經(jīng)想到了，真正令人信服的遞歸經(jīng)典，是漢諾塔問題，請參考遞歸（基礎教程）（彭希仁）2，3兩樓。為了本文的完整，我需要重復一下。

問題：有A、B、C共3根針，其中A針從上到下按從小到大的順序串上了N個金片。要求把金片全部移動到C針上去，可以借助B針，但每次只能移動一片，且移動過程中任何一根針的金片都保持從小到大的順序。

使用遞歸的解題思路是：注意到要把n片金片從A移到C，只要把上面的（n－1）個金片搬到B針上，然后把最底下的金片就可以直接從A移到C。這樣問題就可轉化為把（n－1）個金片從B搬到C針上（金片n搬到C后就不必移動了）。直至使問題轉化為搬動1個金片的問題。

下面是按照上面思路寫出的VBA代碼：

在遞歸外部增加了一個數(shù)組arr1用來保存求解過程，變量q是求解需要的步驟數(shù)量。

Dim arr1, arr2, q Private Sub Hanoi1(ByVal N%, ByVal A$, ByVal B$, ByVal C$) ’“A → C” 來代表把金片從A針移動到C針,即1階漢諾塔問題的解   If N = 1 Then     q = q + 1: arr1(q) = A & "→" & C ’把金片n從A移動到C   Else     Hanoi1 N - 1, A, C, B ’n-1個金片從A到B，以C為過渡     q = q + 1: arr1(q) = A & "→" & C ’把金片n從A移動到C     Hanoi1 N - 1, B, A, C ’n-1個金片從B到C，以A為過渡   End If End Sub

一個看似如此復雜的問題，就這樣解決了，竟然只需要寥寥幾行代碼!

有人說漢諾塔問題是不得不使用遞歸的典型，的確如此，在相當長的時間內，它是唯一的思路。我知道你要說那個美國營養(yǎng)師的解法，但那個思路相比遞歸的解法，要難懂得多，而且，我相信那是對遞歸的結果進行再歸納才形成的（呵呵，你別想說服我，我堅持）。

不錯，我們可以使用循環(huán)來完成上述功能，但這種轉換只是形式上的，它的思想仍然是遞歸的思想。思路和代碼形式的不統(tǒng)一，對程序員實在是很大的痛苦，因為轉換后幾乎已經(jīng)沒有了可讀性，不要說再需要維護和修改了。

看來是需要說說遞歸的好了，當計算機硬件的超快速發(fā)展使內存和速度都不再成為障礙的時候，可以如此簡明高效地解決問題，我們還要拒絕遞歸嗎？

編譯系統(tǒng)開發(fā)人員對遞歸的優(yōu)化研究也從未停止過，而且已經(jīng)成果不菲，對這方面的討論已超出本文的范圍，有興趣的朋友可以參考有關著述，如果我們可以更天真一點去想象的話，也許有一天，編譯系統(tǒng)會使遞歸的代碼效率和使用冗長代碼寫出的循環(huán)代碼相比，一點也不遜色！

9．歸納的步驟

從眾多的個性問題抽象出一般的表述，即謂歸納，雖然歸納不是遞歸獨有的方法，但沒有哪種算法象遞歸這樣依賴這種思想。遞歸設計的全部過程就是將可用遞歸方法解決的問題歸納成通用的、一般的遞歸模式并據(jù)此寫出相應的代碼。我們無法說到每一個問題，萬紫千紅的美妙需要您在未來的探索路上慢慢體味。本文幫您解決三方面的問題，一是歸納出遞歸的基本特征，這在第一個經(jīng)典中已經(jīng)完成；二是給您一些常見問題的演示，這部分放在后面完成；三就是本節(jié)要告訴您的完成這個過程的一般步驟，這些步驟可以保證您正確地做事。

（1）判斷問題是否屬于遞歸問題，如果問題可以劃分為多次相似的操作即為遞歸問題。

（2）確定任務的目標和需要的參數(shù)。任務是指重復的相似操作，如果目標是產(chǎn)生一個確定的計算結果，通常使用Function構造，如果是產(chǎn)生一系列結果或對特定目標的操作，一般使用Sub來完成。參數(shù)包括對問題復雜度進行表達的變量，也包括在兩級遞歸中需要傳遞的數(shù)值。

（3）確定遞歸程序的內部變量和外部變量。對需要輸出一組結果的，為使結果不受遞歸過程的影響，通常使用外部變量或外部對象。

需要說明的，對變量是使用參數(shù)還是使用外部變量或者其它可以保存數(shù)據(jù)的外部對象（如工作表），應以代碼的清晰易讀為原則。應盡量避免使用Static類型的變量或函數(shù)，雖然它可以使原本需要外部的變量巧妙地轉化為內部變量，但通常情況下理解Static要麻煩地多，這不符合使用遞歸的出發(fā)點。

（4）選定“基狀態(tài)”（或出口），并確定在“基狀態(tài)”下應完成的任務。對可用數(shù)值參數(shù)表示復雜度的問題，“基狀態(tài)”應選擇某個參數(shù)的極值（最大值或最小值）。需要注意的是，“基狀態(tài)”并不一定只是一種狀態(tài)，有時是多種可能的狀態(tài)。與“基狀態(tài)”對應的一端即是后面啟動遞歸的“種子”。

（5）確定本遞歸層應完成的工作和與相鄰層的銜接工作，以及以何種方式降低復雜度并引發(fā)遞歸過程。

（6）在調用程序中初始化“種子”值，并保證有關環(huán)境變量設定為應有狀態(tài)，調用遞歸程序。

看到這兒，有些朋友已經(jīng)開始頭大了吧。其實你不要太在意現(xiàn)在理解或記住了多少，這些步驟在實際應用中可能會有一些細小的差異。我的建議是慢慢地培養(yǎng)遵循這些步驟的習慣在學習遞歸的初期是必要，或者你可以對照上述步驟去分析你手頭的遞歸例子。

10．循環(huán)轉化為遞歸

循環(huán)結構內部執(zhí)行的都是相同的任務，所以它一定可以使用遞歸的結構完成。來看一段簡單的代碼：

Sub abc1()   Dim i%   For i = 1 To 10     Cells(i, 3) = Cells(i, 1) + Cells(i, 2)   Next i End Sub

上面這段代碼完成的任務是從第1行到第10行，計算第1列與第2列的和寫入第3列。對照前面提到的步驟分析如下：

（1）參數(shù)為行i,取過程名稱為abc2

Sub abc2(ByVal i As Integer)

（2）出口i>11（種子為1）

If i > 10 Then Exit Sub

（3）本層次要完成的任務為

Cells(i, 3) = Cells(i, 1) + Cells(i, 2)

和相鄰層沒有銜接關系，也不需要做其它工作，直接引發(fā)下層，過程結束

abc2 i + 1 end sub

將上面得到的代碼連起來：

Sub abc2(ByVal i As Integer)   If i > 10 Then Exit Sub   Cells(i, 3) = Cells(i, 1) + Cells(i, 2)   abc2 i + 1 End Sub

（4）在調用過程中用初始值啟動遞歸過程。

Sub cabc()  abc2 1 End Sub

對兩層以上的循環(huán)，可以先將最內層的循環(huán)作為一個遞歸過程，將它外層的循環(huán)當做調用過程，然后逐層進行遞歸化，也可以將各層循環(huán)看作參數(shù)，按照一層循環(huán)的方法進行轉化。下面是使用后一種方法對兩層循環(huán)轉化的例子：

循環(huán)程序： Sub abc3()   Dim i%, j%   For i = 1 To 3     For j = 1 To 5       Cells(i, j) = i * j     Next j   Next i End Sub

轉化的遞歸程序（分析步驟同上）：

Sub abc4(ByVal i As Integer, ByVal j As Integer)   If i > 3 Then Exit Sub   Cells(i, j) = i * j   If j = 5 Then     abc4 i + 1, 1   Else     abc4 i, j + 1   End If End Sub Sub callabc4()   abc4 1, 1 End Sub

也許上面的轉化，包括后面要說的遞歸轉化為循環(huán)，除了給前面說過的結論以實證外，并不一定有太多的現(xiàn)實意義，但起碼讓我們知道，想到了其中的一種方式，同時還有另一種方式的存在，如果你有興趣從各自的立場去理解這兩種方式的話，可以加深對它們的理解。也正因如此，我們通常并不局限于使用一種方式，是選擇遞歸還是循環(huán)抑或兩者共用，應統(tǒng)籌考慮程序的可讀性和效率。接下來要探討遞歸轉化為循環(huán)的方法，在此之前，先來了解一個重要的相關知識。

11．棧

提到棧，總讓人想到匯編等低級語言（請不要和數(shù)據(jù)結構中的“?！毕嗷煜?，后面我們還要說到），它是指在內存中開辟的一端固定一端活動的存儲空間，固定端稱為棧底，活動端稱為棧頂，CPU中有一個叫SP的指針寄存器，始終指向棧頂，數(shù)據(jù)在棧中的存儲遵循后進先出的原則，棧的作用之一就是在發(fā)生子程序調用時進行數(shù)據(jù)的現(xiàn)場保護，調用前，系統(tǒng)會將調用地址、局部變量等壓入棧中，調用完成后再從棧中彈出這些數(shù)據(jù)以使程序繼續(xù)向下運行。在VBA和其它的高級語言中，棧的操作是由編譯系統(tǒng)自動完成的，并不需要程序員的額外干涉。前面已經(jīng)說過，遞歸的過程其實就是棧的工作過程，雖然本文前面給出了一個“黑匣子”理論去理解遞歸，但多數(shù)朋友一定還掛著問號吧，至少那樣理解感覺上有點強詞奪理的樣子，抽象地有點讓人不放心，正因為這樣，“正面”地從棧的工作過程去跟蹤和理解遞歸的工作過程對學習遞歸是有必要的。來看一下“階乘”的例子：

Function Nx2(n)   If n = 1 Then Nx2 = 1: Exit Function   Nx2 = n * Nx2(n - 1) End Function

假定n=3，即要計算Nx2(3)

開始時，棧中數(shù)據(jù)為：空

第1步：

n=3 因不符合第一行代碼的出口條件，第二行代碼需要遞歸，所以將n(3)進棧，調用Nx2(n - 1)即Nx2(2)

此時棧中數(shù)據(jù)為：3

第2步：

n=2 因不符合第一行代碼的出口條件，第二行代碼需要遞歸，所以將n(2)進棧，調用Nx2(n - 1) 即Nx2(1)

此時棧中數(shù)據(jù)為：3，2

第3步：

n=1 因符合第一行代碼的出口條件，返回Nx2(1)的值1

此時棧中數(shù)據(jù)為：3，2

第4步：

n=2 從棧中彈出數(shù)據(jù)2，與返回的Nx2(1)的值1相乘，返回Nx2(2)的值2

此時棧中數(shù)據(jù)為：3

第5步：

n=3 從棧中彈出數(shù)據(jù)3，與返回的Nx2(2)的值2相乘，返回Nx2(3)的值6

此時棧中數(shù)據(jù)為：空遞歸過程完成。上面1-3步通常稱為遞推過程（有點向下級推卸責任的味道），4-5稱為回歸過程（回收下屬的勞動成果）。 可惜我不會做Flash，無法給出最直觀的示意，麻煩您多看幾遍吧，應該還是可以理解的。

現(xiàn)在來說說數(shù)據(jù)結構中的“棧”，它是指按照棧的特點構造的“鏈表”式數(shù)據(jù)，在VBA中，實現(xiàn)“?！钡暮唵畏椒ㄊ鞘褂靡粋€數(shù)組變量和一個單獨的整型變量，數(shù)組用來存儲數(shù)據(jù)，數(shù)組的下界即棧底，上界為棧頂，單獨的變量用作“指針寄存器”，記錄棧頂?shù)奈恢?，進棧時，棧頂值增加1，彈出數(shù)據(jù)時，棧頂值減少1.

歸去來兮！往而返，返而復，是為遞歸~

^^^^

作者：qee用