C#實(shí)現(xiàn)遞歸算法經(jīng)典實(shí)例
一 、遞歸算法簡介
在數(shù)學(xué)與計(jì)算機(jī)科學(xué)中，遞歸是指在函數(shù)的定義中使用函數(shù)自身的方法。
遞歸算法是一種直接或者間接地調(diào)用自身算法的過程。在計(jì)算機(jī)編寫程序中，遞歸算法對(duì)解決一大類問題是十分有效的，它往往使算法的描述簡潔而且易于理解。
遞歸算法解決問題的特點(diǎn)：
(1) 遞歸就是在過程或函數(shù)里調(diào)用自身。
(2) 在使用遞歸策略時(shí)，必須有一個(gè)明確的遞歸結(jié)束條件，稱為遞歸出口。
(3) 遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運(yùn)行效率較低。所以一般不提倡用遞歸算法設(shè)計(jì)程序。
(4) 在遞歸調(diào)用的過程當(dāng)中系統(tǒng)為每一層的返回點(diǎn)、局部量等開辟了棧來存儲(chǔ)。遞歸次數(shù)過多容易造成棧溢出等。所以一般不提倡用遞歸算法設(shè)計(jì)程序。在實(shí)際編程中尤其要注意棧溢出問題。
借助遞歸方法，我們可以把一個(gè)相對(duì)復(fù)雜的問題轉(zhuǎn)化為一個(gè)與原問題相似的規(guī)模較小的問題來求解，遞歸方法只需少量的程序就可描述出解題過程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。但在帶來便捷的同時(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è)比較簡單，直接給出實(shí)現(xiàn)代碼，如圖：
三 、漢諾塔問題
漢諾塔是根據(jù)一個(gè)傳說形成的數(shù)學(xué)問題：
漢諾塔示意圖(圖片來自網(wǎng)絡(luò))
有三根桿子A，B，C。A桿上有N個(gè)(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規(guī)則將所有圓盤移至C桿：
1、每次只能移動(dòng)一個(gè)圓盤；
2、大盤不能疊在小盤上面。
提示：可將圓盤臨時(shí)置于B桿，也可將從A桿移出的圓盤重新移回A桿，但都必須遵循上述兩條規(guī)則。
問：如何移？最少要移動(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è)長度為n的串或者n個(gè)字符(數(shù)字、節(jié)點(diǎn))組成的字符串?dāng)?shù)組，它的全排列共有A(n,n)=n!種。這個(gè)問題也是一個(gè)遞歸的問題。如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è)字母來測(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就可以了。如圖：
總結(jié)
遞歸算法就先說到這里了，希望能夠給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!
相關(guān)文章
這篇文章主要介紹了C#基礎(chǔ)知識(shí)之Partial的使用，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-01-01
用C#操縱IIS（代碼）...2007-03-03
這篇文章主要介紹了c#分頁顯示服務(wù)器上指定目錄下的所有圖片示例,需要的朋友可以參考下2014-05-05
c#創(chuàng)建windows服務(wù)入門教程實(shí)例
windows服務(wù)是windows系統(tǒng)中一類特殊的應(yīng)用程序，一般情況下它們只會(huì)在后臺(tái)運(yùn)行，不會(huì)影響前臺(tái)操作，非常適合做一些不需要用戶參與的而又需要長時(shí)間執(zhí)行的任務(wù)2014-04-04
如何使用Dapper處理多個(gè)結(jié)果集與多重映射實(shí)例教程
Dapper類是一個(gè)開源的數(shù)據(jù)庫操作類，下面這篇文章主要給大家介紹了關(guān)于如何使用Dapper處理多個(gè)結(jié)果集與多重映射的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，需要的朋友可以參考借鑒，下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2018-09-09
C#生成設(shè)置范圍內(nèi)的Double類型隨機(jī)數(shù)的方法
這篇文章主要介紹了C#生成設(shè)置范圍內(nèi)的Double類型隨機(jī)數(shù)的方法,對(duì)于C#的初學(xué)者有很好的借鑒價(jià)值,需要的朋友可以參考下2014-08-08
這篇文章主要介紹了WinForm單例窗體,結(jié)合實(shí)例形式分析了窗體的單例模式定義、實(shí)現(xiàn)與使用技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2016-07-07
在一些公司需要代碼嚴(yán)格的管理,有時(shí)候會(huì)需要用到每個(gè)腳本的頭部做一些介紹,所以下面這篇文章主要給大家介紹了關(guān)于Unity腳本自動(dòng)添加頭部注釋的相關(guān)資料,需要的朋友可以參考下2022-01-01
這篇文章主要介紹了C#自定義基于控制臺(tái)的Timer實(shí)現(xiàn)方法,可以簡單模擬timer控件的相關(guān)功能,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-08-08
這個(gè)結(jié)構(gòu)有點(diǎn)像RIFF文件。。是分段的。但要注意ANNO這個(gè)描述字段 必須是使用2個(gè)字節(jié) 否則ACDSEE無法識(shí)別。2010-03-03