什么是遞歸函數(shù)/方法？ 任何一個方法既可以調(diào)用其他方法也可以調(diào)用自己，而當(dāng)這個方法調(diào)用自己時，我們就叫它遞歸函數(shù)或遞歸方法。 通常遞歸有兩個特點： 1. 遞歸方法一直會調(diào)用自己直到某些條件被滿足 2. 遞歸方法會有一些參數(shù)，而它會把一些新的參數(shù)值傳遞給自己。 那什么是遞歸函數(shù)？函數(shù)和方法沒有本質(zhì)區(qū)別，但函數(shù)僅在類的內(nèi)部使用。以前C#中只有方法，從.NET 3.5開始才有了匿名函數(shù)。 所以，我們最好叫遞歸方法，而非遞歸函數(shù)，本文中將統(tǒng)一稱之為遞歸。 在應(yīng)用程序中為什么要使用遞歸？何時使用遞歸？如何用？ “寫任何一個程序可以用賦值和if-then-else語句表示出來，而while語句則可以用賦值、if-then-else和遞歸表示出來。”（出自Ellis Horowitz的《數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)（C語言版）》 - Fundamentals of Data Structure in C） 遞歸解決方案對于復(fù)雜的開發(fā)來說很方便，而且十分強大，但由于頻繁使用調(diào)用棧（call stack）可能會引起性能問題（有些時候性能極差）。
調(diào)用棧圖示 下面我打算介紹一些例子來幫助你更好的理解遞歸的風(fēng)險和回報。 1. 階乘 階乘（!）是小于某個數(shù)的所有正整數(shù)的乘積。 0! = 1 1! = 1 2! = 2 * 1! = 2 3! = 3 * 2! = 6 ... n! = n * (n - 1)! 下面是計算階乘的一種實現(xiàn)方法（沒有遞歸）：
public long Factorial(int n) { if (n == 0) return 1; long value = 1; for (int i = n; i > 0; i--) { value *= i; } return value; }下面是用遞歸的方法實現(xiàn)計算階乘，與之前的代碼比起來它更簡潔。
public long Factorial(int n) { if (n == 0)//限制條件，對該方法調(diào)用自己做了限制 return 1; return n * Factorial(n - 1); }你知道的，n的階乘實際上是n-1的階乘乘以n，且n>0。 它可以表示成 Factorial(n) = Factorial(n-1) * n 這是方法的返回值，但我們需要一個條件 如果 n=0 返回1。 現(xiàn)在這個程式的邏輯應(yīng)該很清楚了，這樣我們就能夠輕易的理解。2. Fibonacci數(shù)列 Fibonacci數(shù)列是按以下順序排列的數(shù)字： 0,1,1,2,3,5,8,13,21,34,55,…如果F0 = 0 并且 F1= 1 那么Fn = Fn-1 + Fn-2 下面的方法就是用來計算Fn的（沒有遞歸，性能好）
public long Fib(int n) { if (n < 2) return n; long[] f = new long[n+1]; f[0] = 0; f[1] = 1; for (int i = 2; i <= n; i++) { f[i] = f[i - 1] + f[i - 2]; } return f[n]; }如果我們使用遞歸方法，這個代碼將更加簡單，但性能很差。
復(fù)制代碼 代碼如下:public long Fib(int n) { if (n == 0 || n == 1) //滿足條件 return n; return Fib(k - 2) + Fib(k - 1); } <STRONG><SPAN style="FONT-SIZE: medium">3. 布爾組合</SPAN></STRONG>有時我們需要解決的問題比Fibonacci數(shù)列復(fù)雜很多，例如我們要枚舉所有的布爾變量的組合。換句話說，如果n=3，那么我們必須輸出如下結(jié)果： true, true, true true, true, false true, false, true true, false, false false, true, true false, true, false false, false, true false, false, false如果n很大，且不用遞歸是很難解決這個問題的。
復(fù)制代碼 代碼如下:public void CompositionBooleans(string result, int counter) { if (counter == 0) return; bool[] booleans = new bool[2] { true, false }; for (int j = 0; j < 2; j++) { StringBuilder stringBuilder = new StringBuilder(result); stringBuilder.Append(string.Format("{0} ", booleans[j].ToString())).ToString(); if (counter == 1) Console.WriteLine(stringBuilder.ToString()); CompositionBooleans(stringBuilder.ToString(), counter - 1); } }現(xiàn)在讓我們來調(diào)用上面這個方法：
CompositionBoolean(string.Empty, 3);Ian Shlasko建議我們這樣使用遞歸：
public void BooleanCompositions(int count) { BooleanCompositions(count - 1, "true"); BooleanCompositions(count - 1, "false"); } PRivate void BooleanCompositions(int counter, string partialOutput) { if (counter <= 0) Console.WriteLine(partialOutput); else { BooleanCompositions(counter - 1, partialOutput+ ", true"); BooleanCompositions(counter - 1, partialOutput+ ", false"); } }4. 獲取內(nèi)部異常 如果你想獲得innerException，那就選擇遞歸方法吧，它很有用。
public Exception GetInnerException(Exception ex) { return (ex.InnerException == null) ? ex : GetInnerException(ex.InnerException); }為什么要獲得最后一個innerException呢？！這不是本文的主題，我們的主題是如果你想獲得最里面的innerException，你可以靠遞歸方法來完成。 這里的代碼：
return (ex.InnerException == null) ? ex : GetInnerException(ex.InnerException);與下面的代碼等價
if (ex.InnerException == null)//限制條件 return ex; return GetInnerException(ex.InnerException);//用內(nèi)部異常作為參數(shù)調(diào)用自己現(xiàn)在，一旦我們獲得了一個異常，我們就能找到最里面的innerException。例如：
try { throw new Exception("This is the exception", new Exception("This is the first inner exception.", new Exception("This is the last inner exception."))); } catch (Exception ex) { Console.WriteLine(GetInnerException(ex).Message); }我曾經(jīng)想寫關(guān)于匿名遞歸方法的文章，但是我發(fā)覺我的解釋無法超越那篇文章。 5. 查找文件 
我在供你下載的示范項目中使用了遞歸，通過這個項目你可以搜索某個路徑，并獲得當(dāng)前文件夾和其子文件夾中所有文件的路徑。
這個方法似乎不需要滿足任何條件，因為每個目錄如果沒有子目錄，會自動遍歷所有子文件。總結(jié) 我們其實可以用遞推算法來替代遞歸，且性能會更好些，但我們可能需要更多的時間開銷和非遞歸函數(shù)。但關(guān)鍵是我們必須根據(jù)場景選擇最佳實現(xiàn)方式。 James MaCaffrey博士認為盡量不要使用遞歸，除非實在沒有辦法。你可以讀一下他的文章。 我認為： A) 如果性能是非常重要的，請避免使用遞歸 B)如果遞推方式不是很復(fù)雜的，請避免使用遞歸 C) 如果A和B都不滿足，請不要猶豫，用遞歸吧。 例如： 第一節(jié)（階乘）：這里用遞推并不復(fù)雜，那么就避免用遞歸。 第二節(jié)（Fibonacci）：像這樣的遞歸并不被推薦。 當(dāng)然，我并不是要貶低遞歸的價值，我記得人工智能中的重要一章有個極小化極大算法（Minimax algorithm），全部是用遞歸實現(xiàn)的。
新聞熱點
疑難解答
