怎樣學習遞歸？

遞歸要和迭代比較來看。

迭代是重複反饋過程的活動，其目的通常是為了逼近所需目標或結果。每一次對過程的重複稱為一次「迭代」，而每一次迭代得到的結果會作為下一次迭代的初始值，因此迭代是從前往後計算的。

遞歸則是一步一步往前遞推，直到遞歸基礎，尋找一條路徑，然後再由前向後計算。

迭代是從前往後計算的，而遞歸則是先從後往前推，然後再由前往後計算，有「遞」又有「歸」。

通俗來講：引自@lishichengyan

一個小朋友坐在第10排，他的作業本被小組長扔到了第1排，小朋友要拿回他的作業本，可以怎麼辦？

他可以拍拍第9排小朋友，說「幫我拿第1排的本子」，而第9排的小朋友可以拍拍第8排小朋友，說「幫我拿第1排的本子」...如此下去，消息終於傳到了第1排小朋友那裡，於是他把本子遞給第2排，第2排又遞給第3排...終於，本子到手啦！

這就是遞歸，拍拍小朋友的背可以類比函數調用，而小朋友們都記得要傳消息、送本子，是因為他們有記憶力，這可以類比棧。

更嚴謹一些，遞歸蘊含的思想其實是數學歸納法：為了求解問題p（n），首先解決基礎情形p（1），然後假定p（n-1）已經解決，在此基礎上若p（n）得解，那所有問題均得解。

遞歸三要素

遞歸的定義：接受什麼參數，返回什麼值，代表什麼意思。當函數直接或者間接調???時，則發?了遞歸

遞歸的拆解：每次遞歸都是為了讓問題規模變?

遞歸的出?：必須有?個明確的結束條件。因為遞歸就是有「遞」有「歸」，所以必須又有一個明確的點，到了這個點，就不用「遞下去」，而是開始「歸來」。

遞歸的過程

下面這個求 n! 的例子中，遞歸出口（確定遞歸什麼時候結束）是fun(1)=1，遞歸體（確定遞歸求解時的遞歸關係）是fun(n)=n*fun(n-1)，n&>1。

int fun(int n){ if(n==1) return 1; else return n*fun(n-1); }

遞歸經典案例還有斐波那契數列、?階階乘等，想要更好地掌握這個知識點，可以去聽《遞歸四講》哦~

《遞歸四講》這門原價$199的課程，現在$1秒殺！

參與方式：

戳我免費試聽後，添加九章Sunny微信jiuzhang15，回復【知乎遞歸】+試聽報名截圖即可$1購買本課程。

在程序語言中所謂「遞歸」，就是指一個函數「自己調用自己」。遞歸最簡單的應用，就是遍歷一棵樹。

so，就以遍歷樹來進行舉例說明。我們的操場上有一棵樹，樹上長了好多果子。樹下的螞蟻想搞明白樹上到底長了幾個果子，該怎麼辦呢？很簡單，就是一個枝椏一個枝椏爬過去，遇到岔口先左後右。如果發現果子就記個數，如果前面沒有分杈就返回上一個分杈處繼續探索下一個枝椏直到這個分杈處的所有枝椏都被探索完。這就是遞歸實際執行的過程。

在上面的例子裡面，我們可以發現：

1、樹的分杈是有限的；2、有分杈的枝椏，可以看成一顆較小的、且完整的樹；從第二點可知，樹無論如何分杈，不會影響螞蟻的爬行規則。所以，螞蟻可以把每個分杈都當作一顆新的樹來進行探索，無論這棵樹有多大，只要認準這一點，就一定可以完全地爬完整棵樹，一個枝椏都不會落下。於是，這隻小螞蟻就可以用遞歸的方法完整地探索完這棵樹，搞明白到底長了幾個果子了。寫成代碼就是：

int count = 0; void explore() { if (枝椏數量 &> 0) { for (int i = 0; i &< 枝椏數量; i++) { explore(); if (發現果子) count++； } } }

推薦斯坦福大學公開課：抽象編程，裡邊對遞歸講的很細緻很清楚，應該是第7、8集的樣子吧斯坦福大學公開課：抽象編程另外是課程主頁，上邊有一些這門課程的相關資源Stanford School of Engineering樓主看懂了別忘了感謝我

把當前棧空間內的狀態想清楚了，就比較簡單了

再來安利一下之前寫的文章

CuKing：圖解遞歸?

zhuanlan.zhihu.com