遞歸調(diào)用有什么好處一般什么情況下要遞歸？遞歸的基本思想是“調(diào)用你自己”。使用遞歸的方法是直接或間接地調(diào)用自己。其實(shí)遞歸方法體現(xiàn)了“類(lèi)比”和“同步重復(fù)”的思想。它可以用簡(jiǎn)單的程序解決一些復(fù)雜的計(jì)算問(wèn)題，

遞歸調(diào)用有什么好處一般什么情況下要遞歸？

遞歸的基本思想是“調(diào)用你自己”。使用遞歸的方法是直接或間接地調(diào)用自己。

其實(shí)遞歸方法體現(xiàn)了“類(lèi)比”和“同步重復(fù)”的思想。它可以用簡(jiǎn)單的程序解決一些復(fù)雜的計(jì)算問(wèn)題，但計(jì)算量很大。還有一些數(shù)據(jù)結(jié)構(gòu)，如二叉樹(shù)，具有固有的遞歸特性；另外還有一種問(wèn)題，雖然沒(méi)有明顯的遞歸結(jié)構(gòu)，但由于其普遍性，用遞歸程序編寫(xiě)程序比其它方法更容易，如八皇后問(wèn)題、河內(nèi)塔問(wèn)題等對(duì)于遞歸程序，我們應(yīng)該學(xué)會(huì)用遞歸來(lái)解決問(wèn)題。無(wú)論是直接遞歸還是間接遞歸，都需要在當(dāng)前層調(diào)用下一層時(shí)實(shí)現(xiàn)參數(shù)傳遞，獲取下一層返回的結(jié)果，并通過(guò)調(diào)用上一層返回當(dāng)前層的結(jié)果。對(duì)于各層調(diào)用的現(xiàn)場(chǎng)存儲(chǔ)和恢復(fù)，由程序自動(dòng)實(shí)現(xiàn)，無(wú)需人工干預(yù)。因此，在遞歸程序的設(shè)計(jì)中，關(guān)鍵是找出調(diào)用所需的參數(shù)、返回的結(jié)果以及遞歸調(diào)用結(jié)束的條件。例如在階乘函數(shù)fact（n）中，每層需要傳遞一個(gè)自然數(shù)n，返回n*fact（n-1），遞歸調(diào)用結(jié)束的條件是n=0，因此編寫(xiě)相應(yīng)的程序很方便

棧是邏輯結(jié)構(gòu)，不是數(shù)據(jù)結(jié)構(gòu)。這里的堆垛填充不嚴(yán)格。雖然很多試卷給出的答案是stack，但我認(rèn)為這里應(yīng)該填寫(xiě)遞歸stack，也就是說(shuō)，它是用來(lái)存儲(chǔ)被調(diào)用函數(shù)在遞歸工作中執(zhí)行所需要的數(shù)據(jù)，它既有存儲(chǔ)功能，也有存儲(chǔ)功能，有關(guān)系和操作，符合數(shù)據(jù)結(jié)構(gòu)的定義。

數(shù)據(jù)結(jié)構(gòu)中，什么可以作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)？知道的大俠告訴我唄？

如果遞歸級(jí)別太多，則會(huì)出現(xiàn)堆棧溢出異常，因?yàn)槊看握{(diào)用都會(huì)生成新的堆棧幀，并使用此堆棧幀保留當(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á)式，則需要堆棧幀來(lái)保留N和階乘（N-1）的結(jié)果。