如何對(duì)遞歸進(jìn)行理解？既然你想用簡(jiǎn)單的白話來解釋遞歸算法，我就給你解釋一下，確保你能理解。有個(gè)熟悉的故事，正好可以解釋遞歸。這個(gè)故事不斷地調(diào)用自己，遞歸是一個(gè)函數(shù)多次調(diào)用自己。不同的是遞歸不能像這個(gè)故事

如何對(duì)遞歸進(jìn)行理解？

既然你想用簡(jiǎn)單的白話來解釋遞歸算法，我就給你解釋一下，確保你能理解。

有個(gè)熟悉的故事，正好可以解釋遞歸。

這個(gè)故事不斷地調(diào)用自己，遞歸是一個(gè)函數(shù)多次調(diào)用自己。不同的是遞歸不能像這個(gè)故事那樣多次調(diào)用自己。遞歸必須有終止條件，它將在多次調(diào)用后終止。

這個(gè)解釋很口語(yǔ)化。遞歸在函數(shù)體中調(diào)用自己。如果不受控制，它將繼續(xù)調(diào)用自身，直到堆棧溢出。循環(huán)是區(qū)域內(nèi)一段代碼的重復(fù)執(zhí)行，如果不加以控制，就會(huì)形成死循環(huán)。所以無論是遞歸還是循環(huán)，都必須設(shè)置一定的條件來結(jié)束遞歸或循環(huán)。在實(shí)際問題中，有一些問題是遞歸的。用遞歸程序來解決這樣的問題會(huì)感覺更自然，程序也會(huì)更簡(jiǎn)單。然而，遞歸經(jīng)常調(diào)用函數(shù)，并且開銷（內(nèi)存、時(shí)間）很大。有些問題不適合使用。循環(huán)不需要自己調(diào)用，甚至不能調(diào)用函數(shù)，效率很高。但是，遞歸應(yīng)該改為非遞歸如果遞歸級(jí)別太多，就會(huì)導(dǎo)致堆棧溢出異常，因?yàn)槊看握{(diào)用都會(huì)生成一個(gè)新的堆棧幀，并使用這個(gè)堆棧幀來保留當(dāng)前函數(shù)的狀態(tài)值。如果不需要保存狀態(tài)值，則可以重用堆棧幀而不會(huì)導(dǎo)致堆棧溢出。

以n的階乘為例：

正常遞歸：

如果n=3，則每一步都需要保留n值和下一個(gè)函數(shù)的返回值，因此每次調(diào)用都需要?jiǎng)?chuàng)建一個(gè)新的堆棧幀

尾部遞歸：

如果n=3，則每次調(diào)用都可以重用堆棧幀，因?yàn)椴恍枰４鏍顟B(tài)值。

因此，當(dāng)遞歸在當(dāng)前堆棧幀執(zhí)行后完成時(shí)，它不需要保留當(dāng)前堆棧幀，但根據(jù)當(dāng)前堆棧幀的結(jié)果，它可以在進(jìn)入下一個(gè)堆棧幀時(shí)優(yōu)化為尾部遞歸。通常，尾部遞歸需要滿足遞歸調(diào)用是函數(shù)體中最后執(zhí)行的語(yǔ)句。例如，在factorial示例中，要執(zhí)行的最后一條語(yǔ)句是直接調(diào)用factorial（n-1，n*result），而不是表達(dá)式n*factorial（n-1）。如果是表達(dá)式，則需要堆棧幀來保留N和階乘（N-1）的結(jié)果。