程序調用自身的編程技巧稱為遞歸（ recursion）。 一個過程或函數在其定義或說明中又直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合。用遞歸思想寫出的程序往往十分簡潔易懂。 一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。 注意： (1) 遞歸就是在過程或函數里調用自身; (2) 在使用遞增歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口，否則將無限進行下去（死鎖）。 遞歸算法一般用于解決三類問題： (1)數據的定義是按遞歸定義的。(Fibonacci函數) (2)問題解法按遞歸算法實現。(回溯) (3)數據的結構形式是按遞歸定義的。(樹的遍歷，圖的搜索) 遞歸的缺點： 遞歸算法解題的運行效率較低。在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等。 例一 1、 古典問題——有一對兔子，從出生后第3個月起每個月都生一對兔子，小兔子長到第三個月后每個月又生一對兔子，假如兔子都不死，問第三年每個月的兔子總數為多少？（提示：兔子的規律為數列1,1,2,3,5,8,13,21....） 代碼： class Program { static void Main(string[] args) { Program p = new Program(); Console.WriteLine(p.tuzi(7)); } public int tuzi(int n) { if (n == 1 || n == 2) { return 1; } else { return tuzi(n - 1) + tuzi(n - 2); } } } 例二 2、 趣味問題——年齡。有5個人坐在一起，問第五個人多少歲？他說比第4個人大2歲。問第4個人歲數，他說比第3個人大2歲。問第三個人，又說比第2人大兩歲。問第2個人，說比第一個人大兩歲。最后問第一個人，他說是10歲。請問第五個人多大？用遞歸算法實現。 代碼： class Program { static void Main(string[] args) { Program p = new Program(); Console.WriteLine( p.age(5)); } /// /// 遞歸法求歲數 /// /// 有幾個人 /// int age(int n) { int c; if(n==1) return 10; else { c = age(n-1)+2; return c; } } 例三 3、 趣味問題——猴子吃桃。海灘上有一堆桃子，五只猴子來分。第一只猴子把這堆桃子憑據分為五份，多了一個，這只猴子把多的一個扔入海中，拿走了一份。第二只猴子把剩下的桃子又平均分成五份，又多了一個，它同樣把多的一個扔入海中，拿走了一份，第三、第四、第五只猴子都是這樣做的，問海灘上原來最少有多少個桃子？ 代碼： class Program { static void Main(string[] args) { Program p = new Program(); Console.WriteLine( p.PeachNumber(5)); } /// /// 遞歸法求桃子數 /// /// /// int PeachNumber(int n) { if (n == 1) { //最后一個是至少是六個 return 6; } else { return (PeachNumber(n - 1) + 1) * 5; } } 例四 漢諾塔問題。漢諾塔（又稱河內塔）問題是源于印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。用C#編寫一個程序，實現輸出三個圓盤的漢諾塔移動步驟 static void Main(string[] args) { int li_disk_total; System.Console.Write("Please input disk total:"); int.TryParse(System.Console.ReadLine(),out li_disk_total); hanoi(li_disk_total, 'a', 'b', 'c'); System.Console.WriteLine("Move success"); System.Console.ReadLine(); } public static void hanoi(int n,char a,char b,char c) { if (n == 1) move(n, a, c); else { hanoi(n - 1, a, c, b); move(n, a, c); hanoi(n - 1, b, a, c); } } public static void move(int n,char x,char y) { System.Console.WriteLine("Disk " + n.ToString() + " from " + x + " move to " + y); }

總結

以上是生活随笔為你收集整理的递归经典例子的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。