第一個遞迴

Q : 計算 x 的 y 次方值

x 的 y 次方值，就是 x 不斷連乘，總共乘以 y 次的結果
例如 5 的 3 次方就是 5 x 5 x 5 = 125

幾乎不必思考，直接以迴圈撰寫程式

long power(int x, int y)
{

   long r=1;
   while( y-- > 0 ) //用 r 來存放 x 累乘結果，共累乘 y 次
      r=r*x;
   return r;
}

次方值在計算複利、年金時經常會用到，但 C++ 內建的數學運算只有五種
加 + 減 - 乘 * 除 / 餘 %
所以次方這類的計算，就要用函式來處理。但上面的 power 函式沒用遞迴...

遞迴(Recursion)也是函式，透過不斷呼叫自己來運算結果
設計遞迴函式要注意幾點 :
1. 相同的運算方式 (若運算過程沒有規律，就難以用同一段程式來處理)
2. 遞迴參數的調整 (參數若不改變，就難以到達終止條件)
3. 終止條件 (透過自我呼叫時不斷改變的參數，最後要符合終止條件)


1.x 的 y 次方值，就是 x 不斷乘以 x ，總共乘以 y 次的結果
2.次方函式有兩個參數 power( x, y )
3.若計算 5 的 2 次方，主程式呼叫 power( 5, 2 )


step a. power 收到後，呼叫自己計算 5 * power ( 5 , 1 )
step b. power 收到後，呼叫自己計算 5 * power ( 5 , 0 )
step c. power 收到後，達終止條件，傳回 power ( 5 , 0 ) = 1
step b. 收到返回值 1，傳回 5 * power ( 5 , 0 ) = 5 * 1 = 5
step a. 收到返回值 5，傳回 5 * power ( 5 , 1 ) = 5 * 5 = 25

主程式收到結果 25

同樣是思考次方的計算，遞迴要多點想像力，直接看程式會比較清楚

long power(int x, int y)
{
   long r;
   if(y<1) //終止條件，x 的 0 次方等於 1，回傳並結束
     return 1;
   r = x * power(x, y-1); //提一個 x 出來，如 8^5 = 8 * (8^4)
   return r;
}