1 概述 1 概述 本篇文章主要分享演算法部分——遞歸演算法，本文簡要講解幾個經典的遞歸算個發，即乘法階乘、漢諾塔和斐波那契數列。 2 講解部分 2 講解部分 2.1 乘法階乘 問題：求n! 分析： 0!=1; n!=nx(n-1)! code: 2.2 漢諾塔 問題：有三根桿子A，B，C。A桿上有N個 ...
1 概述
本篇文章主要分享演算法部分——遞歸演算法，本文簡要講解幾個經典的遞歸算個發，即乘法階乘、漢諾塔和斐波那契數列。
2 講解部分
2.1 乘法階乘
問題：求n!
分析：
0!=1;
n!=nx(n-1)!
code:
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5 using System.Threading.Tasks;
6
7 namespace ConseDemo
8 {
9 class Program
10 {
11 static void Main(string[] args)
12 {
13 string inputParm=Console.ReadLine();//從控制台輸入參數
14 int n = Int32.Parse(inputParm);
15 Console.WriteLine(JieChengRecursive(n));
16 Console.Read();
17 }
18
19 /// <summary>
20 /// 求n！
21 /// </summary>
22 /// <param name="n">傳入的參數n</param>
23 /// <returns>返回階乘n的結果</returns>
24 public static int JieChengRecursive(int n)
25 {
26 int sum = 1;
27 if (n >= 2)
28 {
29 sum = n * JieChengRecursive(n - 1);
30 }
31 else
32 {
33 return 1;
34 }
35 return sum;
36 }
37 }
38 }
2.2 漢諾塔
問題：有三根桿子A，B，C。A桿上有N個(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規則將所有圓盤移至C桿： 每次只能移動一個圓盤，大盤不能疊在小盤上面
提示：可將圓盤臨時置於B桿，也可將從A桿移出的圓盤重新移回A桿，但都必須遵循上述兩條規則。
問：如何移？最少要移動多少次？
1 static void hannoi(int n, char from, char buffer, char to)
2 {
3 if (n == 1)
4 {
5 Console.WriteLine("Move Disk:{0},from,{1},to,{2}", n, from, to);
6 }
7 else
8 {
9 hannoi(n - 1, from, to, buffer);
10 Console.WriteLine("Move Disk:{0},from,{1},to,{2}", n, from, to);
11 hannoi(n - 1, buffer, from, to);
12 }
13 }
科普：
最早發明這個問題的人是法國數學家愛德華·盧卡斯。
傳說印度某間寺院有三根柱子，上串64個金盤。寺院里的僧侶依照一個古老的預言，以上述規則移動這些盤子；預言說當這些盤子移動完畢，世界就會滅亡。這個傳說叫做梵天寺之塔問題(Tower of Brahma puzzle)。但不知道是盧卡斯自創的這個傳說，還是他受他人啟發。
若傳說屬實，僧侶們需要264 ? 1步才能完成這個任務；若他們每秒可完成一個盤子的移動，就需要5849億年才能完成。整個宇宙現在也不過137億年。
這個傳說有若幹變體：寺院換成修道院、僧侶換成修士等等。寺院的地點眾說紛紜，其中一說是位於越南的河內，所以被命名為“河內塔”。另外亦有“金盤是創世時所造”、“僧侶們每天移動一盤”之類的背景設定。
佛教中確實有“浮屠”（塔）這種建築；有些浮屠亦遵守上述規則而建。“河內塔”一名可能是由中南半島在殖民時期傳入歐洲的。
2.3 斐波那契數列
問題：斐波那契數列指的是這樣一個數列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
特別指出：第0項是0，第1項是第一個1。這個數列從第二項開始，每一項都等於前兩項之和。
分析：
f(0)=0;
f(1)=1;
f(n)=f(n-1)+f(n-2);
code:
1 int Fib(int n)
2 {
3 if (n < 1)
4 {
5 return -1;
6 }
7 if (n == 1 || n == 2)
8 {
9 return 1;
10 }
11 return Fib(n - 1) + Fib(n - 2);
12 }
2.4 總結
關於遞歸演算法，註意兩個條件：(1)迴圈調用函數 (2)函數結束臨界條件
3 版權
- 感謝您的閱讀，若有不足之處，歡迎指教，共同學習、共同進步。
- 博主網址：http://www.cnblogs.com/wangjiming/。
- 極少部分文章利用讀書、參考、引用、抄襲、複製和粘貼等多種方式整合而成的，大部分為原創。
- 如您喜歡，麻煩推薦一下；如您有新想法，歡迎提出，郵箱：[email protected]。
- 可以轉載該博客，但必須著名博客來源。
