柴夥說算法（2）-遞歸

計算機的思維方式是自頂向下的，即遞歸。

----吳軍

開懷一笑

遞歸算法的思想是將一個原始的大問題不斷分解成小問題，直到所有的小問題都可以解決，然後就能夠得到原始問題的解；遞歸算法分爲三個部分，分解的終止條件（否則會陷入死循環中），可解的子問題（對應原問題可求解），以及每次迭代過程中對子問題的處理（該部分可以參見後面內容）；從問題減少的規模來看，它可以分爲兩類，一種是遞歸一次，問題的規模數減1，如階乘和漢諾塔問題，另一種是遞歸一次，問題的規模數減少一半，如二分歸併排序算法；從算法的優勢來看，它主要有兩點優勢：一是將難解的問題分解爲簡單可求解的子問題，一是時間複雜度的減少，在有些問題中，它能夠將O(n*n)的運行時間減少到O(n*log n)，如二分歸併排序算法。當問題的規模數很大時，節省的運行時間非常可觀（吳軍先生說過，設計計算機算法的時候，一開始就要考慮它是爲大規模數據服務的），類似的時間複雜度減少情形還有大名鼎鼎的快速Fourier變換（簡稱FFT）算法；從遞歸一次對子問題的處理方式來看，它可以分爲兩類，一是子問題解的直接合併就是原問題的解，如漢諾談問題，一是需要將子問題的解作適當處理後才是原問題的解，如二分歸併排序。

吳軍先生說，遞歸算法是自頂向下的設計，這種思維方式和人的思維方式不同。如果把它放到生活中去，遞歸算法意味着頂層設計，這是我們很多人所欠缺的。就我個人而言，這種欠缺的原因一是這種思維方式和我們慣常的自下向頂的思維方式不同，一是缺乏相應的基礎以及訓練，這需要平時多注意積累和培養。

參考資料：

[1]離散數學（第五版），屈婉玲，耿素雲，張立昂著，清華大學出版社，2013年，Chap 8.3：遞歸方程的求解和應用

[2]編程珠璣（第二版），（美）JonBentley著，黃倩，錢麗豔譯，人民郵電出版社，2015年，Chap8：算法設計技術（其中的算法值得閱讀，關於數組的相鄰數字和的最大值問題，文中給出了一種理論上最優的線性運行時間）

[3]第099封信：遞歸—計算機思維和人的思維最大的不同，吳軍著，吳軍的谷歌方法論，2018-05-16

[4]漢諾塔

https://baike.baidu.com/item/%E6%B1%89%E8%AF%BA%E5%A1%94/3468295?fr=aladdin

[5]如何理解和掌握快速傅里叶变换的计算和概念？

https://www.zhihu.com/question/20456490