程式呼叫自身的編程技巧稱為遞迴(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)); } /// <summary> /// 遞歸法求歲數 /// </summary> /// <param name="n">有幾個人</param> /// <returns></returns> 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)); } /// <summary> /// 遞歸法求桃子數 /// </summary> /// <param name="n"></param> /// <returns></returns> int PeachNumber(int n) { if (n == 1) { //最後一個是至少是六個 return 6; } else { return (PeachNumber(n - 1) + 1) * 5; } }
以上就是這次關於遞迴的整理,希望對你的學習有所幫助。