遞歸是一種應(yīng)用非常廣泛的算法(或者編程技巧)。遞歸求解問題的分解過程，去的過程叫“遞”，回來的過程叫“歸”。

遞歸需要滿足的三個(gè)條件：1. 一個(gè)問題的解可以分解為幾個(gè)子問題的解；2. 這個(gè)問題與分解之后的子問題，除了數(shù)據(jù)規(guī)模不同，求解思路完全一樣；3. 存在遞歸終止條件。

問題：N級臺(tái)階(比如100級)，每次可走1步或者2步，求總共有多少種走法？

分析：如果有大于2級的n級臺(tái)階，那么假如第一次跳一級臺(tái)階，剩下還有n-1級臺(tái)階，有f(n-1)種跳法，假如第一次條2級臺(tái)階，剩下n-2級臺(tái)階，有f(n-2)種跳法。這就表示f(n)=f(n-1)+f(n-2)，即斐波那契數(shù)列。假設(shè)只有一個(gè)臺(tái)階，那么只有一種跳法，那就是一次跳一級，f(1)=1；如果有兩個(gè)臺(tái)階，那么有兩種跳法，第一種跳法是一次跳一級，第二種跳法是一次跳兩級，f(2)=2。

編寫遞歸代碼的關(guān)鍵是，只要遇到遞歸，我們就把它抽象成一個(gè)遞推公式，不用想一層層的調(diào)用關(guān)系，不要試圖用人腦去分解遞歸的每個(gè)步驟。

遞歸代碼要警惕重復(fù)計(jì)算

為了避免重復(fù)計(jì)算，我們可以通過一個(gè)數(shù)據(jù)結(jié)構(gòu)(比如散列表)來保存已經(jīng)求解過的 f(k)。

遞歸代碼要警惕堆棧溢出

我們可以通過在代碼中限制遞歸調(diào)用的最大深度的方式來解決這個(gè)問題，遞歸調(diào)用超過一定深度(比如 1000)之后，我們就不繼續(xù)往下再遞歸了，直接拋出異常。

怎么將遞歸代碼改寫為非遞歸代碼？

遞歸本身就是借助棧來實(shí)現(xiàn)的，如果我們自己在內(nèi)存堆上實(shí)現(xiàn)棧，手動(dòng)模擬入棧、出棧過程，便可以將遞歸改成非遞歸。

總結(jié)

以上是生活随笔為你收集整理的递归Java_递归的Java实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。