C#資料結構與算法系列（十二）：遞歸（Recursion）

1.介紹

簡單的說：遞歸就是方法自己調用自己，每次調用時傳入不同的變量，遞歸有助于程式設計者解決複雜的問題，同時也讓代碼變得整潔

2.規則

執行一個方法時，就建立一個新的受保護的獨立空間（棧空間）

方法的局部變量是獨立的，不會互相影響，比如n變量

如果方法中使用的是引用類型變量（比如數組），就會共享該引用類型的資料

遞歸必須向退出遞歸條件逼近，否則就是無限遞歸了，出現***Error,死龜

當一個方法執行完畢，或者遇到return,就會傳回，遵守誰調用，就将結果傳回給誰，同時當方法執行完畢或者傳回時，該方法也就執行完畢

3.遞歸能解決什麼問題

1.各種數學問題如：八皇後問題，漢諾塔，階乘問題，迷宮問題等

2.各種算法也會使用到遞歸，比如快排、歸并排序，二分查找，分治算法

4.示例：列印問題、階乘問題

1.圖解：

 2.代碼示例

public class RecursionTest
    {
        public static void Test(int num)
        {
            if (num > 2)
            {
                Test(num - 1);
            }

            System.Console.WriteLine("num=" + num);
        }

        public static int Factorial(int num)
        {
            if (num == 1)
            {
                return 1;
            }

            return Factorial(num - 1) * num;
        }

        public static void RecursionDemo()
        {
            Test(4);

            System.Console.WriteLine("\n5的階乘是:"+Factorial(5));
        }
    }      

3.示範圖