今天我班的大神心血來潮，居然找了本算法的書看起來了，裡面有很多經典的例子，大神在編程方面是一張白紙，所以看到講解遞歸的部分時就傻了眼，比如書上講解求Fibonacci數列時就用的是遞歸算法，相當的簡潔明了，代碼如下：
unsigned long fibonacci (int n)
{
if (n <= 2)
{
return 1;
}
else
{
return fibonacci(n-1) + fibonacci(n-2);
}
}
我對於遞歸的思想很是贊同的，有化繁為簡，分而治之的想法在裡面，就好像很多編程思想一樣，如：動態規劃等等。但我認為大部分的遞歸想法僅僅是在人的接受能力上進行了化簡，這是後話。其實遞歸算法是很好理解的，只是大神還不習慣罷了。如上的程序是運用數列的遞推公式非常明白的寫出來的。但就如我所言，這個遞歸算法其實浪費了很多CPU資源，我們可以仔細分析一下，比如：
f(5) = f(4) + f(3)
= f(3) + f(2) + f(2) + f(1)
= f(2) + f(1) + f(2) + f(2) + f(1)
= 1 + 1 + 1 + 1 + 1
這裡計算f(5)就用到了12個加法，其實我們可以發現我們把f(3)算出來後f(4)其實不用像我這樣拆開來算的，直接用f(3)的結果就行了，換句話說即充分利用所求項等於前兩項的和，而這兩項之間又有關系，不難想到，可以寫出一個不使用遞歸的算法如下：
unsigned long fibonacci (int n)
{
unsigned long f0, f1, temp;
int i;
if (n <= 2)
{
return 1;
}
else
{
for (f0 = f1 = 1, i = 3; i <= n; i++)
{
temp = f0 + f1;
f0 = f1;
f1 = temp;
}
return f1;
}
}
這個算法用一個變量temp保存兩個前項之和，然後及時更新f0和f1，最後那個return返回temp也是可以的，因為我的temp保存的內容和f1一樣。可以再看一下我們計算f(5)時做了多少個加法，仔細一數是僅僅只用了三個加法，大大減少了運算開銷，而其上面那個遞歸程序因為在不停的調用函數，所以還會消耗一定的函數調用棧。為什麼大牛們都說除非是實在太繁雜，否則別用遞歸，原因可見一二。我把我的想法向班上的大牛說了下，他馬上告訴我一個在一本書上的更快的算法，這著實讓我們班一群小草很是震驚，他說是這麼想的，由我上面那個非遞歸的算法可以推出在算f(n)時最多不會超過n-2個加法，要加快程序只能把加法繼續減少，這裡才是思維的精髓，事實上一般減少加法的方法就是使用乘法，不過後來我想到乘法器比加法器要復雜，所以能夠提高的效率我們並不可知，不過這種思想確實不一般。曾經在線性代數課上老師也介紹過一個偽Fibonacci矩陣，即一個2*2的矩陣，第一行元素為1,1，第二行為1,0。我們發現f(n)的值就是這個矩陣n-2次方後在第一行上的兩個元素的和，如f(5)就等於把這個矩陣3次方後，此時第一行的兩個元素分別為3和2，所以f(5) = 3 + 2。這個要推也很簡單，算一兩個就發現這個規律了，依據這個思想，他寫下了如下的代碼：
unsigned long fibonacci (int n)
{
unsigned long a, b, c, d;
int i;
if (n <= 2)
{
return 1;
}
else
{
matrix_power(1,1,1,1,n-2,&a,&b,&c,&d);
return f1;
}
}
//計算矩陣的n次方
matrix_power(unsigned long a, unsigned long b, unsigned long c, unsigned long d, int n,
unsigned long *aa, unsigned long *bb, unsigned long *cc, unsigned long *dd)
{
unsigned long xa, xb, xc, xd;
if (1 == n)
{
*aa = a, *bb = b, *cc = c, *dd = d;
}
else if (n & 0x01 == 1)
{
matrix_power(a, b, c, d, n-1, &xa, &xb, *xc, *xd);
*aa = a * xa + b * xc;
*bb = a * xb + b * xd;
*cc = c * xa + d * xc;
*dd = c * xb + d * xd;
}
else
{
matrix_power(a, b, c, d, n>>1, &xa, &xb, &xc, &xd);
*aa = xa * xa + xb * xc;
*bb = xa * xb + xb * xd;
*cc = xc * xa + xd * xc;
*dd = xc * xb + xd * xd;
}
}
我們還可以發現這段代碼在求矩陣的n次方時用了一個分治的思想，判斷n的奇偶，如果是偶數就遞歸求出n/2次方再平方，若是奇數就寫成M*M的偶數次方，這裡居然又用了遞歸，倒！原本是不想遞歸才繞了這麼一大圈子，現在又回到原點了，實在不好意思去求大牛了， 只好自己動手豐衣足食，不就是求一個矩陣的n次方嗎？看我也不用遞歸。矩陣弄在一起太復雜，我就假設是求一個數m的n次方吧！如果是按遞歸算法求m的n次方，然後把每次遞歸調用時傳入的n值列出來我發現一個驚人的事實，那就是每次調用時n均為2的倍數，這時我似乎看到了些什麼，於是我仔細研究了下，加上大膽的猜想，終於讓我發現了一個規律，在求m的n次方時可以把n寫成二進制數，找到二進制位為1的位，然後可以將n寫成2的這些位所對應的權值之和，於是m的n次方就能寫成m的這些權值次方的和了，比如求m的9次方，將9寫成二進制數為1001，所以9 = 2的0次方 + 2的3次方，令a = 2的0次方，b = 2的3次方，則m的9次方 = m的a次方 + m的b次方。這樣一來我只需要遍歷n的二進制位就行了，於是我迅速修改了上面求矩陣的n次方的代碼：
//改變出參的值
getTemp(unsigned long **aa, unsigned long **bb, unsigned long **cc, unsigned long **dd,
unsigned long a, unsigned long b, unsigned long c, unsigned long d)
{
unsigned long tempa = **aa, tempb = **bb, tempc = **cc, tempd = **dd;
tempa = **aa * a + (**bb) * c;
tempb = **aa * b + (**bb) * d;
tempc = **cc * a + (**dd) * c;
tempd = **cc * b + (**dd) * d;
**aa = tempa;
**bb = tempb;
**cc = tempc;
**dd = tempd;
}
//計算矩陣的n次方修正版
matrix_power(unsigned long a, unsigned long b, unsigned long c, unsigned long d, int n,
unsigned long *aa, unsigned long *bb, unsigned long *cc, unsigned long *dd)
{
unsigned long xa = a, xb = b, xc = c, xd = d;
unsigned long tempa = a, tempb = b, tempc = c, tempd = d;
int flageven = 0, flag = 1;
if (!(n & 0x01UL))
{
flageven = 1;
}
while (n > 0)
{
if (1 == (n & 0x01UL))
{
if (1 == flag)
{
*aa = a;
*bb = b;
*cc = c;
*dd = d;
flag = 0;
if (1 == flageven)
{
getTemp(&aa, &bb, &cc, &dd, xa, xb, xc, xd);
}
}
else
{
getTemp(&aa, &bb, &cc, &dd, xa, xb, xc, xd);
}
}
tempa = xa * a + xb * c;
tempb = xa * b + xb * d;
tempc = xc * a + xd * c;
tempd = xc * b + xd * d;
xa = tempa;
xb = tempb;
xc = tempc;
xd = tempd;
n >>= 1;
}
}
忙活了半個晚上終於結束了這場和遞歸的戰斗，至此這個Fibonacci數列總算被階段性拿下，一個我認為可以接受的非遞歸算法出爐。關於遞歸還有很多可以討論一下，不過現在已經早上了，我還是先去休息一下，過段時間再來和大家分享一下自己的遞歸心得。同時也希望大家對我上面的算法有什麼建議或是置疑都可以提出來，我們共同探討，互聯網最方便的應該是交流了，我期待您的關注。
本文出自 “菜鳥浮出水” 博客，請務必保留此出處http://rangercyh.blog.51cto.com/1444712/292806
