經(jīng)典實例講解C#遞歸算法

更新時間：2020年06月05日 14:18:43 作者：雲(yún)霏霏

這篇文章主要用實例講解C#遞歸算法的概念以及用法，文中代碼非常詳細，幫助大家更好的參考和學習，感興趣的朋友可以了解下

一、遞歸算法簡介

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

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

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

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

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

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

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

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

1、 Fibonacci數(shù)列

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

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …，總之，就是第N(N > 2)個數(shù)等于第(N - 1)個數(shù)和(N - 2)個數(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、階乘

還有就是求一個數(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;
  }

三、漢諾塔問題

漢諾塔是根據(jù)一個傳說形成的數(shù)學問題：

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

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

　　1、每次只能移動一個圓盤；

　　2、大盤不能疊在小盤上面。

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

　　問：如何移？最少要移動多少次？

下面是漢諾塔的遞歸求解實現(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);
   }
  }

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

四、排列組合

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

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

用遞歸算法實現(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();
  }

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

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

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

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

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

此時聲明全局變量，如下：

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

這個時候，我們修改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é)果保存到鏈表中了。用的時候，我們只要遍歷NodeList就可以了。如圖：