遞歸是在運行過程中調(diào)用自身。遞歸的條件如下：學(xué)習(xí)了解遞歸和尾遞歸的區(qū)別？如果遞歸級別太多，則會出現(xiàn)堆棧溢出異常，因為每次調(diào)用都會生成一個新的堆棧幀，用于保留當(dāng)前函數(shù)的狀態(tài)值。如果不需要保存狀態(tài)值，則可

遞歸是在運行過程中調(diào)用自身。遞歸的條件如下：

學(xué)習(xí)了解遞歸和尾遞歸的區(qū)別？

如果遞歸級別太多，則會出現(xiàn)堆棧溢出異常，因為每次調(diào)用都會生成一個新的堆棧幀，用于保留當(dāng)前函數(shù)的狀態(tài)值。如果不需要保存狀態(tài)值，則可以重用堆棧幀而不會導(dǎo)致堆棧溢出。

以n的階乘為例：

正常遞歸：

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

尾部遞歸：

如果n=3，則每次調(diào)用都可以重用堆棧幀，因為不需要保存狀態(tài)值。

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

尾遞歸究竟是好是壞？

遞歸算法是一種直接或間接調(diào)用自身的算法。在計算機程序設(shè)計中，遞歸算法對于解決一大類問題是非常有效的。它往往使算法的描述簡潔易懂。遞歸是在過程或函數(shù)中調(diào)用自身。在使用遞歸策略時，必須有一個顯式的遞歸結(jié)束條件，稱為遞歸退出。遞歸算法通常非常簡單，但效率較低。因此，不建議使用遞歸算法來設(shè)計程序。在遞歸調(diào)用過程中，系統(tǒng)打開一個棧來存儲每一層的返回點和局部數(shù)量。太多的遞歸很容易導(dǎo)致堆棧溢出。

程序的遞歸算法與非遞歸有什么區(qū)別？

遞歸和迭代都是循環(huán)類型。簡單地說，遞歸就是反復(fù)調(diào)用函數(shù)本身來實現(xiàn)循環(huán)。迭代是由函數(shù)中的某些代碼實現(xiàn)的循環(huán)。迭代與普通循環(huán)的區(qū)別在于，循環(huán)代碼中參與運算的變量也是保存結(jié)果的變量，當(dāng)前保存的結(jié)果是下一次循環(huán)計算的初始值。在遞歸循環(huán)中，當(dāng)滿足終止條件時，循環(huán)將逐層返回。迭代使用計數(shù)器結(jié)束循環(huán)。當(dāng)然，在許多情況下，各種循環(huán)是混合的，這取決于具體的需要。遞歸示例，例如，給定一個整數(shù)數(shù)組，使用半查詢返回數(shù)組中指定值的索引，假設(shè)數(shù)組已排序。為了便于描述，假設(shè)所有的元素都是正數(shù)，數(shù)組的長度是2的整數(shù)倍。半查詢是一種查詢，它比遍歷所有元素快得多。迭代的經(jīng)典例子是實數(shù)的累加，例如計算從1到100的所有實數(shù)之和。

遞歸與迭代的區(qū)別？

尾部遞歸：程序中只有一個遞歸語句，它位于末尾。單向遞歸：指程序中的遞歸語句，在程序運行之前已經(jīng)完成，如斐波那契數(shù)列。這樣做的共同特點是在轉(zhuǎn)換非遞歸時不必保存分支路由

如果這樣的CFG離開了遞歸，遞歸下降法和語法分析中的LL（1）就不能處理它，因為程序會陷入遞歸，不能前進。Cfga-> BA“a”-> BA“| e與前面的表達式相同，但所有語法的第一項是終止符，它消除了左遞歸。有消除左遞歸的算法，一般編譯原理書中會介紹，不是很復(fù)雜。