一 、遞歸算法簡(jiǎn)介

在數(shù)學(xué)與計(jì)算機(jī)科學(xué)中，遞歸是指在函數(shù)的定義中使用函數(shù)自身的方法。

　　遞歸算法是一種直接或者間接地調(diào)用自身算法的過(guò)程。在計(jì)算機(jī)編寫(xiě)程序中，遞歸算法對(duì)解決一大類問(wèn)題是十分有效的，它往往使算法的描述簡(jiǎn)潔而且易于理解。
遞歸算法解決問(wèn)題的特點(diǎn)：

　　(1) 遞歸就是在過(guò)程或函數(shù)里調(diào)用自身。

　　(2) 在使用遞歸策略時(shí)，必須有一個(gè)明確的遞歸結(jié)束條件，稱為遞歸出口。

　　(3) 遞歸算法解題通常顯得很簡(jiǎn)潔，但遞歸算法解題的運(yùn)行效率較低。所以一般不提倡用遞歸算法設(shè)計(jì)程序。

　　(4) 在遞歸調(diào)用的過(guò)程當(dāng)中系統(tǒng)為每一層的返回點(diǎn)、局部量等開(kāi)辟了棧來(lái)存儲(chǔ)。遞歸次數(shù)過(guò)多容易造成棧溢出等。所以一般不提倡用遞歸算法設(shè)計(jì)程序。在實(shí)際編程中尤其要注意棧溢出問(wèn)題。

　　借助遞歸方法，我們可以把一個(gè)相對(duì)復(fù)雜的問(wèn)題轉(zhuǎn)化為一個(gè)與原問(wèn)題相似的規(guī)模較小的問(wèn)題來(lái)求解，遞歸方法只需少量的程序就可描述出解題過(guò)程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。但在帶來(lái)便捷的同時(shí)，也會(huì)有一些缺點(diǎn)，也即：通常用遞歸方法的運(yùn)行效率不高。 

二 、Fibonacci數(shù)列和階乘

1、 Fibonacci數(shù)列

提到遞歸，我們可能會(huì)想到的一個(gè)實(shí)例便是斐波那契數(shù)列。斐波那契數(shù)列就是如下的數(shù)列：

  0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …，總之，就是第N(N > 2)個(gè)數(shù)等于第(N - 1)個(gè)數(shù)和(N - 2)個(gè)數(shù)的和。用遞歸算法實(shí)現(xiàn)如下：

public static int Fibonacci(int n)
  {
   if (n < 0) return -1;
   if (n == 0) return 0;
   if (n == 1) return 1;
   return Fibonacci(n - 1) + Fibonacci(n - 2);
  }

2、階乘

還有就是求一個(gè)數(shù)的階乘，也會(huì)用到遞歸，這個(gè)比較簡(jiǎn)單，直接給出實(shí)現(xiàn)代碼，如圖：

public static int Factorial (int n)
  {
  int sum = 0;
  if (0==n)
  return 1;
  else
  sum = n * Factorial(n 一1) ;
  return sum;
  }

三 、漢諾塔問(wèn)題 

漢諾塔是根據(jù)一個(gè)傳說(shuō)形成的數(shù)學(xué)問(wèn)題：

　　      漢諾塔示意圖(圖片來(lái)自網(wǎng)絡(luò))

 有三根桿子A，B，C。A桿上有N個(gè)(N>1)穿孔圓盤(pán)，盤(pán)的尺寸由下到上依次變小。要求按下列規(guī)則將所有圓盤(pán)移至C桿：

　　1、每次只能移動(dòng)一個(gè)圓盤(pán)；

　　2、大盤(pán)不能疊在小盤(pán)上面。

　　提示：可將圓盤(pán)臨時(shí)置于B桿，也可將從A桿移出的圓盤(pán)重新移回A桿，但都必須遵循上述兩條規(guī)則。

　　問(wèn)：如何移？最少要移動(dòng)多少次？

 下面是漢諾塔的遞歸求解實(shí)現(xiàn)(C#代碼)：

public static void hannoi(int n, string from, string buffer, string to)
  {
   if (n == 1)
   {
   Console.WriteLine("Move disk " + n + " from " + from + " to " + to);
   }
   else
   {
   hannoi(n - 1, from, to, buffer);
   Console.WriteLine("Move disk " + n + " from " + from + " to " + to);
   hannoi(n - 1, buffer, from, to);
   }
  }

其運(yùn)行結(jié)果如圖(大家可以跟上面的gif圖片對(duì)比一下):

四 、排列組合

1、輸出任意個(gè)數(shù)字母、數(shù)字的全排列

　　對(duì)于一個(gè)長(zhǎng)度為n的串或者n個(gè)字符(數(shù)字、節(jié)點(diǎn))組成的字符串?dāng)?shù)組，它的全排列共有A(n, n)=n!種。這個(gè)問(wèn)題也是一個(gè)遞歸的問(wèn)題。如1,2,3，全排列可得到：{123,132,213,231,312,321}。

用遞歸算法實(shí)現(xiàn)代碼如下：

public static void Permutation(string[] nums, int m, int n)
  {
   string t;
   if (m < n - 1)
   {
   Permutation(nums, m + 1, n);
   for (int i = m + 1; i < n; i++)
   {
    //可抽取Swap方法
    t = nums[m];
    nums[m] = nums[i];
    nums[i] = t;
    
    Permutation(nums, m + 1, n);

    //可抽取Swap方法
    t = nums[m];
    nums[m] = nums[i];
    nums[i] = t;
   }
   }
   else
   {for (int j = 0; j < nums.Length; j++)
   {
    Console.Write(nums[j]);
   }
   Console.WriteLine();
   }
  }

調(diào)用代碼如下：

static void Main(string[] args)
  {
   Nums = new string[] { "a", "b", "c" };
   Permutation(Nums, 0, Nums.Length);
   Console.ReadKey();
  }

這里傳入一個(gè)string數(shù)組，abc三個(gè)字母來(lái)測(cè)試，輸出如下圖：

2、將全排列結(jié)果保存到鏈表中

　　有時(shí)候，我們需要將全排列的結(jié)果保存，然后做其他的處理，我們可以將結(jié)果保存到一個(gè)鏈表中。我們定義如下類作為鏈表的節(jié)點(diǎn)，代碼如下：

public class Node
 {
  public string value { get; set; }
  public Node nextNode { get; set; }

  public Node(string value)
  {
   this.value = value;
   this.nextNode = null;
  }
 }

 此時(shí)聲明全局變量，如下：

public static List<Node> NodeList = new List<Node>();

這個(gè)時(shí)候，我們修改Permutation方法，如下：

public static void Permutation(string[] nums, int m, int n)
  {
   string t;
   if (m < n - 1)
   {
   Permutation(nums, m + 1, n);
   for (int i = m + 1; i < n; i++)
   {
    //可抽取Swap方法
    t = nums[m];
    nums[m] = nums[i];
    nums[i] = t;
    
    Permutation(nums, m + 1, n);

    //可抽取Swap方法
    t = nums[m];
    nums[m] = nums[i];
    nums[i] = t;
   }
   }
   else
   {
   Node root = null;
   Node currentNode;
   for (int j = 0; j < nums.Length; j++)
   {
    currentNode = new Node(nums[j]);
    currentNode.nextNode = root;
    root = currentNode;
   }
   NodeList.Add(root);
   }
  }

這樣，我們執(zhí)行了Permutation方法后，就將結(jié)果保存到鏈表中了。用的時(shí)候，我們只要遍歷NodeList就可以了。如圖：

 遞歸算法就先說(shuō)到這里了。談到算法，就必需提數(shù)據(jù)結(jié)構(gòu)，看來(lái)真的要“學(xué)到老了”~~

以上就是經(jīng)典實(shí)例講解C#遞歸算法的詳細(xì)內(nèi)容，更多關(guān)于c#遞歸算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論