首頁猿問遞歸還是迭代？

遞歸還是迭代？

算法與數(shù)據(jù)結(jié)構(gòu) 算法

LEATH 2019-07-11 14:56:55

遞歸還是迭代？如果我們使用循環(huán)而不是遞歸，那么性能會受到影響嗎？反之亦然，在算法中，兩者都可以達(dá)到相同的目的嗎？檢查給定的字符串是否為回文。我見過許多程序員使用遞歸作為一種方法，在一個簡單的迭代算法能夠滿足要求的情況下炫耀它。編譯器在決定使用什么方面起著至關(guān)重要的作用嗎？

查看完整描述

3 回答

慕勒3428872

TA貢獻(xiàn)1848條經(jīng)驗獲得超6個贊

遞歸可能會更昂貴，這取決于遞歸函數(shù)是否是尾遞歸(最后一行是遞歸調(diào)用)。尾遞歸應(yīng)得到編譯器的認(rèn)可，并對其迭代對應(yīng)進(jìn)行優(yōu)化(同時保持代碼中的簡潔、清晰的實現(xiàn))。

我會用最有意義的方式來編寫算法，對于那些必須在幾個月或幾年內(nèi)維護(hù)代碼的可憐的傻瓜(不管是你自己還是其他人)來說，它是最清晰的。如果遇到性能問題，那么請分析代碼，然后通過迭代實現(xiàn)進(jìn)行優(yōu)化。你也許想調(diào)查一下回憶錄和動態(tài)規(guī)劃.

反對回復(fù) 2019-07-11