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

遞歸算法一般上是否都可以用棧進(jìn)行模擬？

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

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