首頁(yè) 猿問(wèn) 遞歸比循環(huán)更快嗎？

遞歸比循環(huán)更快嗎？

性能測(cè)試

慕工程0101907 2019-07-29 10:15:12

遞歸比循環(huán)更快嗎？我知道遞歸有時(shí)比循環(huán)更清晰，而且我不會(huì)詢問(wèn)何時(shí)應(yīng)該使用遞歸迭代，我知道有很多問(wèn)題已經(jīng)存在。我要問(wèn)的是，遞歸是否比循環(huán)更快？對(duì)我來(lái)說(shuō)，似乎總是能夠改進(jìn)循環(huán)并讓它比遞歸函數(shù)更快地執(zhí)行，因?yàn)檠h(huán)不會(huì)不斷地設(shè)置新的堆棧幀。我特別關(guān)注在遞歸是處理數(shù)據(jù)的正確方法的應(yīng)用程序中遞歸是否更快，例如在一些排序函數(shù)，二叉樹等中。

查看完整描述

3 回答

慕尼黑的夜晚無(wú)繁華

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

這取決于使用的語(yǔ)言。你寫了'語(yǔ)言不可知'，所以我舉一些例子。

在Java，C和Python中，與迭代（通常）相比，遞歸相當(dāng)昂貴，因?yàn)樗枰峙湫碌亩褩?。在某些C編譯器中，可以使用編譯器標(biāo)志來(lái)消除此開銷，這會(huì)將某些類型的遞歸（實(shí)際上是某些類型的尾調(diào)用）轉(zhuǎn)換為跳轉(zhuǎn)而不是函數(shù)調(diào)用。

在函數(shù)式編程語(yǔ)言實(shí)現(xiàn)中，有時(shí)，迭代可能非常昂貴，并且遞歸可能非常便宜。在許多情況下，遞歸轉(zhuǎn)換為簡(jiǎn)單的跳轉(zhuǎn)，但是更改循環(huán)變量（這是可變的）有時(shí)需要一些相對(duì)繁重的操作，尤其是在支持多個(gè)執(zhí)行線程的實(shí)現(xiàn)上。由于mutator和垃圾收集器之間的交互，如果兩者可能同時(shí)運(yùn)行，在某些環(huán)境中突變是昂貴的。

我知道在一些Scheme實(shí)現(xiàn)中，遞歸通常比循環(huán)更快。

簡(jiǎn)而言之，答案取決于代碼和實(shí)現(xiàn)。使用您喜歡的任何風(fēng)格。如果您使用的是函數(shù)式語(yǔ)言，則遞歸可能會(huì)更快。如果您使用命令式語(yǔ)言，迭代可能會(huì)更快。在某些環(huán)境中，這兩種方法都會(huì)導(dǎo)致生成相同的程序集（將其放入管道并對(duì)其進(jìn)行抽吸）。

附錄：在某些環(huán)境中，最好的選擇既不是遞歸也不是迭代，而是高階函數(shù)。這些包括“map”，“filter”和“reduce”（也稱為“fold”）。這些不僅是首選樣式，不僅通常更清晰，而且在某些環(huán)境中，這些函數(shù)是第一個(gè)（或唯一）從自動(dòng)并行化中獲得提升的功能 - 因此它們可以比迭代或遞歸快得多。Data Parallel Haskell就是這種環(huán)境的一個(gè)例子。

列表推導(dǎo)是另一種選擇，但這些通常只是迭代，遞歸或更高階函數(shù)的語(yǔ)法糖。

反對(duì) 回復(fù) 2019-07-29