旷世神医,小说排行榜

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案

用C#實(shí)現(xiàn)遞歸方法-創(chuàng)新互聯(lián)

原文地址：http://www.codeproject.com/Articles/142292/Recursive-methods-in-Csharp
作者：Shahin Khorshiadnia
譯者：Tony Qu

目前創(chuàng)新互聯(lián)已為上千余家的企業(yè)提供了網(wǎng)站建設(shè)、域名、虛擬主機(jī)、網(wǎng)站托管運(yùn)營(yíng)、企業(yè)網(wǎng)站設(shè)計(jì)、大冶網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長(zhǎng)，共同發(fā)展。

Codeproject評(píng)分:

用C#實(shí)現(xiàn)遞歸方法下載演示程序 – 20.7K

用C#實(shí)現(xiàn)遞歸方法下載源代碼 – 38.9K

什么是遞歸函數(shù)/方法？

任何一個(gè)方法既可以調(diào)用其他方法也可以調(diào)用自己，而當(dāng)這個(gè)方法調(diào)用自己時(shí)，我們就叫它遞歸函數(shù)或遞歸方法。

通常遞歸有兩個(gè)特點(diǎn)：

1. 遞歸方法一直會(huì)調(diào)用自己直到某些條件被滿足

2. 遞歸方法會(huì)有一些參數(shù)，而它會(huì)把一些新的參數(shù)值傳遞給自己。

那什么是遞歸函數(shù)？函數(shù)和方法沒有本質(zhì)區(qū)別，但函數(shù)僅在類的內(nèi)部使用。以前C#中只有方法，從.NET 3.5開始才有了匿名函數(shù)。

所以，我們最好叫遞歸方法，而非遞歸函數(shù)，本文中將統(tǒng)一稱之為遞歸。

在應(yīng)用程序中為什么要使用遞歸？何時(shí)使用遞歸？如何用？

“寫任何一個(gè)程序可以用賦值和if-then-else語句表示出來，而while語句則可以用賦值、if-then-else和遞歸表示出來?！保ǔ鲎訣llis Horowitz的《數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)（C語言版）》 - Fundamentals of Data Structure in C）

遞歸解決方案對(duì)于復(fù)雜的開發(fā)來說很方便，而且十分強(qiáng)大，但由于頻繁使用調(diào)用棧（call stack）可能會(huì)引起性能問題（有些時(shí)候性能極差）。

我們來看一看下面這個(gè)圖：

用C#實(shí)現(xiàn)遞歸方法

調(diào)用棧圖示

下面我打算介紹一些例子來幫助你更好的理解遞歸的風(fēng)險(xiǎn)和回報(bào)。

1. 階乘

階乘（!）是小于某個(gè)數(shù)的所有正整數(shù)的乘積。

0! = 1
1! = 1
2! = 2 * 1! = 2
3! = 3 * 2! = 6
...
n! = n * (n - 1)!

下面是計(jì)算階乘的一種實(shí)現(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;
}

下面是用遞歸的方法實(shí)現(xiàn)計(jì)算階乘，與之前的代碼比起來它更簡(jiǎn)潔。

public long Factorial(int n)
{
    if (n == 0)//限制條件，對(duì)該方法調(diào)用自己做了限制
        return 1;
    return n * Factorial(n - 1);
}

你知道的，n的階乘實(shí)際上是n-1的階乘乘以n，且n>0。

它可以表示成 Factorial(n) = Factorial(n-1) * n

這是方法的返回值，但我們需要一個(gè)條件

如果 n=0 返回1。

現(xiàn)在這個(gè)程式的邏輯應(yīng)該很清楚了，這樣我們就能夠輕易的理解。

2. Fibonacci數(shù)列

Fibonacci數(shù)列是按以下順序排列的數(shù)字：

0,1,1,2,3,5,8,13,21,34,55,…

如果F₀ = 0 并且 F₁= 1 那么F_n = F_n-1 + F_n-2

下面的方法就是用來計(jì)算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];
}

如果我們使用遞歸方法，這個(gè)代碼將更加簡(jiǎn)單，但性能很差。

public long Fib(int n)
{
    if (n == 0 || n == 1) //滿足條件
        return n;
    return Fib(k - 2) + Fib(k - 1);
}
3. 布爾組合

有時(shí)我們需要解決的問題比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很大，且不用遞歸是很難解決這個(gè)問題的。

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)用上面這個(gè)方法：

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);
}

為什么要獲得最后一個(gè)innerException呢？！這不是本文的主題，我們的主題是如果你想獲得最里面的innerException，你可以靠遞歸方法來完成。

這里的代碼：

return (ex.InnerException == null) ? ex : GetInnerException(ex.InnerException);

與下面的代碼等價(jià)

if (ex.InnerException == null)//限制條件
   return ex;
return GetInnerException(ex.InnerException);//用內(nèi)部異常作為參數(shù)調(diào)用自己

現(xiàn)在，一旦我們獲得了一個(gè)異常，我們就能找到最里面的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. 查找文件

用C#實(shí)現(xiàn)遞歸方法

我在供你下載的示范項(xiàng)目中使用了遞歸，通過這個(gè)項(xiàng)目你可以搜索某個(gè)路徑，并獲得當(dāng)前文件夾和其子文件夾中所有文件的路徑。

private Dictionary errors = new Dictionary();
private List result = new List();

private void SearchForFiles(string path)
{
   try
   {
      foreach (string fileName in Directory.GetFiles(path))//Gets all files in the current path
      {
          result.Add(fileName);
      }

      foreach (string directory in Directory.GetDirectories(path))//Gets all folders in the current path
      {
         SearchForFiles(directory);//The methods calls itself with a new parameter, here!
      }
   }
   catch (System.Exception ex)
   {
      errors.Add(path, ex.Message);//Stores Error Messages in a dictionary with path in key
   }
}

這個(gè)方法似乎不需要滿足任何條件，因?yàn)槊總€(gè)目錄如果沒有子目錄，會(huì)自動(dòng)遍歷所有子文件。

總結(jié)

我們其實(shí)可以用遞推算法來替代遞歸，且性能會(huì)更好些，但我們可能需要更多的時(shí)間開銷和非遞歸函數(shù)。但關(guān)鍵是我們必須根據(jù)場(chǎng)景選擇最佳實(shí)現(xiàn)方式。

James MaCaffrey博士認(rèn)為盡量不要使用遞歸，除非實(shí)在沒有辦法。你可以讀一下他的文章。

我認(rèn)為：

A) 如果性能是非常重要的，請(qǐng)避免使用遞歸

B)如果遞推方式不是很復(fù)雜的，請(qǐng)避免使用遞歸

C) 如果A和B都不滿足，請(qǐng)不要猶豫，用遞歸吧。

例如：

第一節(jié)（階乘）：這里用遞推并不復(fù)雜，那么就避免用遞歸。

第二節(jié)（Fibonacci）：像這樣的遞歸并不被推薦。

當(dāng)然，我并不是要貶低遞歸的價(jià)值，我記得人工智能中的重要一章有個(gè)極小化極大算法（Minimax algorithm），全部是用遞歸實(shí)現(xiàn)的。

但是如果你決定使用隊(duì)規(guī)方法，你最好嘗試用存儲(chǔ)來優(yōu)化它。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

標(biāo)題名稱：用C#實(shí)現(xiàn)遞歸方法-創(chuàng)新互聯(lián)
URL分享：http://fisionsoft.com.cn/article/dddjos.html

新聞中心

其他資訊