遞歸代碼都轉(zhuǎn)為非遞歸可以嗎

先說答案，這是肯定的，所有遞歸代碼都可以轉(zhuǎn)為非遞歸代碼。

之所以所有的遞歸都能轉(zhuǎn)為迭代算法是因?yàn)檫f歸借助函數(shù)調(diào)用，函數(shù)調(diào)用本身就是基于調(diào)用棧這種結(jié)構(gòu)實(shí)現(xiàn)的，只不過這一切都是自動(dòng)完成的，我們當(dāng)然也可以用代碼手動(dòng)模擬出來。

我們知道將遞歸調(diào)用全部展開后其實(shí)會形成一棵樹，把遞歸轉(zhuǎn)為非遞歸無非就是在遍歷這棵樹，那么遍歷樹就有很多技術(shù)了，基于棧的深度優(yōu)先遍歷Depth-first traversal，或者基于隊(duì)列的廣度優(yōu)先遍歷breadth-first traversal都是可以的：

說會遞歸轉(zhuǎn)為非遞歸這個(gè)話題，更理論一些的解釋是這樣的，不管是遞歸還是非遞歸，這兩者都是圖靈完備的，既然是圖靈完備，那么它們在表達(dá)能力上就是等價(jià)的，不存在誰不能轉(zhuǎn)為誰的問題。

只不過這存在一個(gè)難易程度的問題。

大家都知道尾遞歸最容易轉(zhuǎn)為非遞歸的迭代形式，本質(zhì)上是這棵樹不是多叉的而是單叉的，單叉的不就退化成鏈表了嘛，遍歷鏈表當(dāng)然是簡單的，但如果是多叉的話問題就沒那么簡單了， 這里最有趣的是不存在一種模板可以讓我們直接用套路的形式把遞歸轉(zhuǎn)為非遞歸 ，因此這里存在一個(gè)問題：為什么你要把遞歸轉(zhuǎn)為非遞歸呢？因?yàn)樽罱K你會發(fā)現(xiàn)將遞歸轉(zhuǎn)為非遞歸無非就是你自己接手了編譯器本來已經(jīng)替你完成的工作， 你會發(fā)現(xiàn)自己在手動(dòng)模擬函數(shù)調(diào)用 。

遞歸的優(yōu)勢很明顯：代碼簡潔，容易理解和維護(hù)，其為人詬病的地方在于執(zhí)行效率“可能”沒有非遞歸版本的高，但你最好理解這句話到底在說什么，到底哪里效率就不高了？