由斐波那契數列引發的思考

週末時間,還是不能放鬆學習~

人一吃飽飯沒事幹就愛瞎想,你看古今中外的哲學家們,整天思考宇宙人生,從哪來到哪去的問題,要是肚子都沒吃飽哪有那閒情去扯這些呢?馬斯洛需求層次理論可以瞭解一下.

等等,好像跑題了,言歸正傳.話說下午閒來無事,就在某論壇瞎逛,無意之中瞥到了斐波那契數列,於是乎,想起了有一回面試被要求用遞歸的方式手寫求斐波那契數列第n個數......我想了大概15分鐘,因為一開始腦子想的都是數組和加for循環的求解思路,突然靈感一現,峰迴路轉,最終只用3行代碼搞定了!寫出來的程序是這樣的:

private static int fibonacci(int n) {
 if (n <= 2) {
 return 1;
 }
 return fibonacci(n - 1) + fibonacci(n - 2);
 }

突然,我又腦洞大開,何不試試用遞歸的方式實現在控制檯打印九九乘法表咧~

實現在控制檯打印輸出九九乘法表相信大部分coder剛入門的時候都寫過,甚至有些面試場合也會要求手寫代碼或排序等算法.

面對這個需求,我的第一反應就是用嵌套for循環來解決,寫出來的代碼是這樣的:

 private static void multipTable() {
 for (int i = 1; i < 10; i++) {
 for (int j = 1; j < 10; j++) {
 System.out.print(j + "x" + i + "=" + i * j + " ");
 if (i == j) {
 //換行並跳出當前循環
 System.out.println();
 break;
 }
 }
 }
 }

時間複雜度是O(n^2),代碼看似很簡潔也實現功能了,但問題就是:逼格不夠高!那咋辦咧,得想個逼格更高的實現方式,遞歸,說的就是你!思忖一番,寫出的代碼長這個樣子:

private static void multipTable(int n) {
 if (n == 1) {
 System.out.println("1x1=1");
 } else {
 multipTable(n - 1);
 for (int i = 1; i <= n; i++) {
 System.out.print(i + "x" + n + "=" + i * n + " ");
 }
 System.out.println();
 }
 }

調用的時候傳值n=9,嗯,不錯,是有遞歸思想,可還有for循環呀,這麼寫逼格是提高了一丟丟,然鵝代碼不夠優雅.咳咳,沒辦法,平日受夠產品經理折磨的我,閒下來還要折磨自己,我已經被生活摧殘成這個樣子了嗎?

仔細捋捋思路,本問的關鍵是要解決列值和行值能找到一種關係,上一種解決方式找到了關係,就是列值的最大值小於行值,但是是通過for循環來體現的.這次我找到了一種新的關係,9x9,8x8,7x7...1x1,意思是假如現在是最後一行,我計算完後,壓進棧中,這時要計算第八行,那怎麼進入第八行呢,第九行減一行作為行數,列數等於行數,不就遞歸調用了嗎?

好,行數的問題解決了,那列數呢,從每一行的最後一列計算到第一列怎麼搞?你看,列數不是等於行數了嘛,那這個時候在第八行最後一列,是8x8,我讓行數不變,列數減一遞歸調用就能實現了,出口就是列數要d等1,等於1說明已經計算到第一列,要往上一行遞歸了!

所以,綜上所述,行遞歸函數的出口是row=1,列遞歸函數的出口是col=1;

row == 1 && col == 1,則是整個遞歸函數的出口;

最終沒有for循環的純遞歸版本是這樣的:

private static void multipTable(int row, int col) {
 //遞歸函數的出口
 if (row == 1 && col == 1) {
 System.out.println("1x1=1");
 }
 if (row > 1) {
 if (col > 1) {
 //列遞歸函數
 multipTable(row, col - 1);
 } else {
 //行遞歸函數
 multipTable(row - 1, row - 1);
 }
 System.out.print(col + "x" + row + "=" + row * col + " ");
 if (row == col) {
 System.out.println();
 }
 }
 }

總算是搞定了,激動之餘,回顧一下寫的這些代碼,發現了一個問題,也不是所有的算法遞歸寫的代碼都更簡潔的咯,而且在代碼易讀性上,for循環更清晰易懂(這個因人而異).除了這些,遞歸還有什麼劣勢嗎?總結了一下遞歸的優缺點:

優點：代碼普遍更簡潔,尤其是在樹的遍歷算法中.

缺點：

1.遞歸由於是函數調用自身，而函數調用是有時間和空間的消耗的：每一次函數調用，都需要在內存棧中分配空間以保存參數、返回地址以及臨時變量，而往棧中壓入數據和彈出數據都需要時間。

2.遞歸中很多計算都是重複的，由於其本質是把一個問題分解成兩個或者多個小問題，多個小問題存在相互重疊的部分，則存在重複計算，如斐波那契數列的遞歸實現,可以自己用筆在紙上畫一下屬性圖.

3.可能會發生棧溢出，其實每一次函數調用會在內存棧中分配空間，而每個進程的棧的容量是有限的，當調用的層次太多時，就會超出棧的容量，從而導致棧溢出。