遞歸算法一般上是否都可以用棧進行模擬？遞歸調(diào)用本身需要使用系統(tǒng)堆棧，每次分配函數(shù)內(nèi)存和堆棧都需要時間。然而，這個過程并不需要太多時間?？梢哉f，簡單遞歸本身并不比非遞歸慢多少。然而，在實際應(yīng)用中，人們會

遞歸算法一般上是否都可以用棧進行模擬？

遞歸調(diào)用本身需要使用系統(tǒng)堆棧，每次分配函數(shù)內(nèi)存和堆棧都需要時間。然而，這個過程并不需要太多時間?？梢哉f，簡單遞歸本身并不比非遞歸慢多少。然而，在實際應(yīng)用中，人們會發(fā)現(xiàn)遞歸在處理一些問題，特別是遞歸問題時效率很低。這個問題是由重復(fù)計算引起的例如，要遞歸求解斐波那契數(shù)列的第n項，一般的遞歸公式是f（n）=f（n-1）f（n-2）f（2）=1F（1）=1請試著模擬運行這個遞歸的計算機，你會發(fā)現(xiàn)其中一項f（x）不是只計算一次的。當(dāng)您計算f（5）時，您將嘗試計算f（4）和f（3），但是當(dāng)您計算f（4）時，您還需要計算f（3），因此f（3）被調(diào)用兩次。假設(shè)這個過程是指數(shù)展開的，效率會隨著n的增加而提高，要解決這個問題，我們可以用記憶法的思想。定義內(nèi)存數(shù)組R，并將函數(shù)體更改為：Define（n）：如果定義了R[n]，則返回NR[n]和其他人一樣F（n）=F（n-1）F（n-2）在返回值之前，將其記在r[n]中。改進后的遞歸函數(shù)的效率與遞歸算法幾乎相同

需要將節(jié)點的訪問信息放入棧中，并簡要描述過程：當(dāng)前節(jié)點是根節(jié)點，需要逐個遞歸遍歷其所有子節(jié)點。在訪問子節(jié)點之前，需要將當(dāng)前節(jié)點的信息和訪問的子節(jié)點數(shù)：push（root，1）然后訪問他的子節(jié)點，push（son，1）然后訪問孫子節(jié)點如果孫子節(jié)點是葉子節(jié)點，則在進行遞歸調(diào)用時需要在堆棧中記錄當(dāng)前訪問的節(jié)點對于for循環(huán)，運行時實際上會在調(diào)用之前記錄程序狀態(tài)（循環(huán)變量=multive，這意味著您訪問了子節(jié)點）。當(dāng)然，當(dāng)您手動模擬堆棧時，必須記錄狀態(tài)值才能實現(xiàn)這一點