遞歸算法學習

1.基本定義：遞歸就是函數或過程直接或間接調用本身的算法。

2.使用遞歸算法的要求：

   (1). 必須是重複工作，而且此工作可以多次分成多次重複的操作，且每次分開規模都要減小。

   (2). 重複操作之間要緊密相連，上一次操作為下一次做準備(通常前一次的輸出作為下一次的輸入)。

3.使用遞歸時應注意的問題：

   (1).使用遞歸時必須明确遞歸的結束條件，即遞歸出口

   (2).遞歸算法解題顯得很簡潔，但運作效率比較低；不提倡用遞歸算法來設計程式。

   (3).遞歸調用過程中系統為每一層的傳回點和局部變量開辟棧來存儲，遞歸次數多了可能會造成棧溢出，是以不提倡用遞歸設計程式。

4. 遞歸分類：直接調用和間接調用

    (1). 直接調用：函數或過程直接調用本身

    f(int x)

   {

　　...

　　f(y);   ---------------->直接調用本身

　　...

    }

(2). 間接調用：兩個方法或過程分别調用對方

      procedure a(形參)

　　{

　　　　.......

　　　　procedure b(形參);------------------->調用過程b

　　　　.......

　　}

　　procedure b(形參)

　　{

　　　　........

　　　　procedure a(形參)--------------->調用過程a

　　　　........

　　}

　　5. 基本的遞歸示例：

      (1). n!

      n! = n *(n -1) *(n-2) * ....*3 *2 *1

      是以可以看成重複的操作，且上一次的輸出是下一次的輸入。 n!= n*((n-1)!)

     c#遞歸實作n!的代碼：

namespace Testn
{
    class Program
    {
        static void Main(string[] args)
        {

            int n = 0;
            long res = 0;
            Console.WriteLine("請輸入n的值!");
            n = int.Parse(Console.ReadLine());

            res = GetJieCheng(n);
            Console.WriteLine("{0}！= {1}",n,res );
        }
        public static long GetJieCheng(int n)
        {
            if (n == 1)
            {
                return 1;
            }
            else
            {
                return n * GetJieCheng(n - 1);    

            }
            
        }
    }
}
           

轉載于:https://www.cnblogs.com/shuming/archive/2011/01/20/1940587.html