[C Programming] 數值自乘遞迴解

如果n與m是正整數，那麼m^n就是把m連乘n次，
這是一個很沒有效率的方法。請寫一個更有效率的程式，
並且分析您的程式中一共用了多少個乘法。
你應該以少於n-1個乘法做為設計準則。

解：
對於遞迴關係而言，最重要的就是分析n的值的狀況，
然後做出相對應的動作，且要有終止的條件。
就此例而言，我們可以將n每次分成2份，
如果n是偶數的話就可以變成(m^(n/2))*(m^(n/2))，
奇數的話則會多出一個m，
最後分到沒得分(0)的時候就傳回m^0=1。
如此一來遞迴做到最後我們只需要負擔最多2*log n次的乘法(底數為2)，
最少則是log n次。(在前面每次拆分都是偶數的情況下。)

Code：

#include <stdio.h>
#include <stdlib.h>

unsigned long recursive_power(unsigned long m, unsigned long n)
{
 unsigned long temp;
 if(n == 0)       // m ^ 0 = 1
  return 1;
 else if ( n & 0x01UL == 0) // even
 { 
  temp = recursive_power(m, n >> 1); // m, n/2
  return temp * temp;
 }
 else              // odd
  return m * recursive_power(m, n-1);
}

int main(int argc, char *argv[])
{ 
 unsigned long m, n;
 m = 5;
 n = 11;
 printf("\n%ld^%ld = %ld\n",m , n, recursive_power(m,n));
 system("PAUSE");
 return 0;
}