文章目錄

• 簡介
• 遞歸樹和階乘
• 斐波那契數(shù)列
• GCD最大公約數(shù)
• N中選K
• 0-1背包問題
• 硬幣找零問題
• 數(shù)組的最長遞增子序列
• 旅行商問題

簡介

在之前我們介紹的很多數(shù)據(jù)結(jié)構(gòu)和算法都用到了遞歸，遞歸非常容易理解，用途也很廣泛，但是有一個缺點(diǎn)就是需要保存棧的狀態(tài)，如果遞歸次數(shù)太多會造成棧溢出的問題。

本文將會講解常見的棧的應(yīng)用，并使用遞歸樹形象的展示其遞歸的過程。

遞歸樹和階乘

遞歸樹是迭代過程的一種圖像表述。遞歸樹往往被用于求解遞歸方程， 它的求解表示比一般的迭代會更加的簡潔與清晰。

看一個最簡單的使用遞歸的例子，就是階乘。

比如 4！=4* 3！= 4 * 3 * 2！ = 4 * 3 * 2 * 1！ =24。

我們用一個動畫來詳細(xì)看一下階乘的遞歸調(diào)用和它的遞歸樹。

遞歸樹的運(yùn)行過程是先構(gòu)建遞歸樹，然后從最底層得到運(yùn)行結(jié)果，一層一層的進(jìn)行回歸，最后得到最終的結(jié)果。

總結(jié)

以上是生活随笔為你收集整理的看动画学算法之:递归和递归树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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