TA貢獻(xiàn)1886條經(jīng)驗(yàn) 獲得超2個(gè)贊
有一些很好的解釋遞歸在這個(gè)線程中，這個(gè)答案是關(guān)于為什么不應(yīng)該在大多數(shù)語(yǔ)言中使用它。*在大多數(shù)重要的命令式語(yǔ)言實(shí)現(xiàn)中(即C、C+、Basic、Python、Ruby、Java和C#的每個(gè)主要實(shí)現(xiàn))迭代法比遞歸要好得多。
要了解原因，請(qǐng)遍歷上述語(yǔ)言用于調(diào)用函數(shù)的步驟：
函數(shù)的代碼運(yùn)行
執(zhí)行所有這些步驟都需要時(shí)間，通常比遍歷循環(huán)所需的時(shí)間稍長(zhǎng)一些。然而，真正的問(wèn)題在于步驟1。當(dāng)許多程序啟動(dòng)時(shí)，它們?yōu)槎褩７峙湟恍K內(nèi)存，當(dāng)它們耗盡內(nèi)存時(shí)(通常，但并不總是由于遞歸)，程序會(huì)因?yàn)槎褩Ｒ绯?
因此，在這些語(yǔ)言中，遞歸更慢，它使您容易崩潰。盡管如此，仍然有一些關(guān)于使用它的爭(zhēng)論。一般來(lái)說(shuō)，遞歸編寫(xiě)的代碼一旦知道如何讀取，就會(huì)更短、更優(yōu)雅。
語(yǔ)言實(shí)現(xiàn)者可以使用一種叫做尾叫優(yōu)化可以消除某些類(lèi)型的堆棧溢出。簡(jiǎn)單地說(shuō)：如果一個(gè)函數(shù)的返回表達(dá)式只是函數(shù)調(diào)用的結(jié)果，那么您不需要在堆棧中添加一個(gè)新的級(jí)別，您可以為被調(diào)用的函數(shù)重用當(dāng)前的級(jí)別。遺憾的是，很少有命令式語(yǔ)言實(shí)現(xiàn)內(nèi)置了尾叫優(yōu)化。
*?我喜歡遞歸。我最喜歡的靜態(tài)語(yǔ)言根本不使用循環(huán)，遞歸是重復(fù)執(zhí)行某些事情的唯一方法。我只是不認(rèn)為遞歸在沒(méi)有調(diào)優(yōu)的語(yǔ)言中是個(gè)好主意。
*順便說(shuō)一句，ArrangeString函數(shù)的典型名稱(chēng)是“JOIN”，如果您選擇的語(yǔ)言還沒(méi)有實(shí)現(xiàn)，我會(huì)感到驚訝。
TA貢獻(xiàn)1811條經(jīng)驗(yàn) 獲得超6個(gè)贊
A child couldn't sleep, so her mother told her a story about a little frog, who couldn't sleep, so the frog's mother told her a story about a little bear, who couldn't sleep, so the bear's mother told her a story about a little weasel... who fell asleep. ...and the little bear fell asleep; ...and the little frog fell asleep; ...and the child fell asleep.
TA貢獻(xiàn)1795條經(jīng)驗(yàn) 獲得超7個(gè)贊
struct Node {
Node* next;
};int length(const Node* list) {
if (!list->next) {
return 1;
} else {
return 1 + length(list->next);
}
}舉報(bào)