成都小程序開發(fā)開發(fā)人員經(jīng)常使用算法將問題分解為更容易解決的更小的塊。這種分而治之的方法使得為了解決每個問題，您可以多次調(diào)用同一個函數(shù)來處理每個部分。
在編程中，遞歸發(fā)生在方法調(diào)用自身時，并在達(dá)到基本情況時終止?；厩闆r是一個條件語句，它執(zhí)行返回語句而不是再次調(diào)用相同的函數(shù)，結(jié)束循環(huán)。遞歸的典型用途包括分而治之算法和解決連續(xù)出現(xiàn)的問題，例如計算斐波那契數(shù)列或階乘。
在這篇文章中，我們將討論成都小程序開發(fā)中的遞歸，以及如何編寫計算數(shù)字階乘的遞歸方法。您將了解如何在成都小程序開發(fā)中使用遞歸，何時比其他方法更好，以及實現(xiàn)遞歸函數(shù)時的最佳實踐。
Java 中用于遞歸的代碼相對簡單，尤其是與迭代方法相比。遞歸可以幫助您編寫使用更少內(nèi)存的軟件，因為一旦函數(shù)返回，變量就會被刪除。遞歸函數(shù)是純函數(shù)，這意味著它們的輸出僅取決于它們的輸入?yún)?shù)。
了解成都小程序開發(fā)中遞歸的最簡單方法之一是檢查打印數(shù)字階乘的函數(shù)。
您可以通過將一個數(shù)乘以所有小于它本身的正整數(shù)來計算階乘。在本節(jié)中，您將看到遞歸代碼與基于循環(huán)的代碼之間的比較。
例如，5 的階乘為 120，可以這樣表示：
階乘 (5) = 5 * (4 * (3 * (2 * 1)))
請注意這是如何形成一個級數(shù)的：5 的階乘等于 5 乘以 4 的階乘，4 乘以 3 的階乘，依此類推。遞歸的基本情況是 0。當(dāng)輸入?yún)?shù)達(dá)到 0 時，您將從方法主體返回 1。
以下函數(shù)計算作為參數(shù)傳遞的數(shù)字的階乘——一次使用 For 循環(huán)，然后再次使用遞歸。在主入口點調(diào)用此方法并傳遞一個參數(shù)。您可以通過提供 5 作為輸入?yún)?shù)來對此進(jìn)行測試，程序返回 120。
您可以使用 For 和 While 循環(huán)在成都小程序開發(fā)中執(zhí)行階乘。
在構(gòu)建遞歸函數(shù)時，您可以添加邊緣情況來縮短遞歸。如果下一個遞歸調(diào)用將是基本情況，則進(jìn)行短路測試。您可以在數(shù)字等于或小于 0 時返回 2 并開始遞歸，而不是僅在數(shù)字等于或小于 0 時返回 1。
請記住，短路需要編寫一個包裝函數(shù)來對參數(shù)執(zhí)行條件檢查。這通常是不鼓勵的，因為包裝器的價值需要更高。
為了處理短路，向類中添加一個新的成員方法作為遞歸函數(shù)的包裝器。包裝函數(shù) factorial 調(diào)用內(nèi)部方法factorialRecursive開始遞歸。此代碼具有相同的輸出，但在執(zhí)行過程中又跳過了一步，因為當(dāng)數(shù)字變?yōu)?2 時它會短路。
現(xiàn)在讓我們使用“遞歸和階乘”部分中的方法來研究決定遞歸和非遞歸方法的一些因素。
在成都小程序開發(fā)中，遞歸以多種方式提高性能，包括：
記憶化
Memoization 跳過已經(jīng)計算輸出并存儲在內(nèi)存中的遞歸情況。這可以防止重復(fù)計算，因為存儲了輸出并提高了軟件的性能。這種方法利用緩存來提高使用遞歸的性能。
查找階乘的代碼使用緩存變量來存儲以前使用的值。
此外，遞歸方法還僅依賴于輸入并包含業(yè)務(wù)邏輯，而沒有底層技術(shù)方面，例如堆棧管理。這允許工程師編寫具有更少內(nèi)存和更少副作用（方法范圍之外的狀態(tài)更改，例如系統(tǒng)參數(shù)）的軟件。
此外，它對特定算法很有用，例如樹遍歷。深度優(yōu)先搜索算法使用堆棧來執(zhí)行搜索。因此，您可以將算法編寫為遞歸函數(shù)，與迭代方法相比，這更容易編寫。例如，比較使用遞歸和迭代方法的前序遍歷代碼。
最后，一些表達(dá)式，尤其是在數(shù)學(xué)運算中使用的表達(dá)式，具有特定的符號。這些操作的輸入最常見的表示法是前綴、中綴和后綴。固定是操作數(shù)在操作中的位置。這允許遞歸函數(shù)輕松復(fù)制操作而無需額外的包裝器。您可以使用上述表達(dá)式從數(shù)組構(gòu)建樹，反之亦然。這有助于在一維內(nèi)存結(jié)構(gòu)（例如 RAM）中表示復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，例如樹。
遞歸也有其局限性。首先，遞歸函數(shù)反復(fù)調(diào)用自身，這會導(dǎo)致堆棧因參數(shù)溢出而導(dǎo)致程序過早終止。在成都小程序開發(fā)中，每個程序的堆棧空間都是有限的，而堆的限制則較少。因此，當(dāng)程序試圖使用大量堆?？臻g時，它會收到 StackOverflowException，此時程序會繼續(xù)壓入堆棧但不會彈出并達(dá)到限制。
另一方面，堆不是后進(jìn)后出操作 (LIFO)，因此程序可以在系統(tǒng)允許的范圍內(nèi)向堆推送盡可能多的數(shù)據(jù)。
此外，當(dāng)遞歸函數(shù)執(zhí)行函數(shù)調(diào)用作為最后一個語句時，Java 編譯器無法優(yōu)化使用尾遞歸的遞歸方法。相反，遞歸函數(shù)將函數(shù)調(diào)用作為頭遞歸中的第一條語句執(zhí)行。
“處理邊緣情況”部分中的代碼演示了沒有一個函數(shù)是尾遞歸。factorialRecursion 是非尾遞歸（不要與頭遞歸混淆），因為它作為函數(shù)的結(jié)果運行。
此方法使用一個變量來存儲所有數(shù)字的乘積。它運行一個循環(huán)，該循環(huán)從我設(shè)置為2的變量開始并返回產(chǎn)品。請注意，大于 2 的數(shù)字必須相乘，直到i等于數(shù)字參數(shù)本身。當(dāng)滿足循環(huán)條件時，迭代停止。
迭代風(fēng)格使得定義迭代計數(shù)、內(nèi)存管理和計算停止的時間變得更加容易。這也允許更好地控制堆棧增長。它有助于避免成都小程序開發(fā)程序中的 StackOverflowException。
同樣，迭代方法不需要包裝函數(shù)。因此，它們避免了任何不需要的額外堆棧輸入。這就是為什么通常不鼓勵通過縮短遞歸來獲得一次性性能改進(jìn)的原因。
然而，對于基于序列的問題，例如計算階乘或斐波那契數(shù)列，迭代方法通常更難編寫。遞歸通常會產(chǎn)生一種更優(yōu)雅的方法，它可以用更少的代碼行產(chǎn)生相同的結(jié)果。
在遞歸函數(shù)中，處理所有可能的邊緣情況以從遞歸函數(shù)返回。如果您不處理邊緣情況，您的遞歸可能會永遠(yuǎn)運行，導(dǎo)致您的程序由于 StackOverflowException 錯誤而過早終止。遞歸中的短路并不總是最好的方法，因為您通常必須圍繞遞歸函數(shù)編寫包裝函數(shù)。代替短路包裝函數(shù)，對遞歸方法內(nèi)部的邊緣情況和函數(shù)可以接受的參數(shù)應(yīng)用條件檢查。
此外，請記住堆棧不會跟蹤已處理的參數(shù)。這會導(dǎo)致您的遞歸函數(shù)重復(fù)處理相同的參數(shù)。為避免這種重復(fù)并降低時間復(fù)雜度，您應(yīng)該始終在處理后使用記憶來存儲參數(shù)。
遞歸函數(shù)允許成都小程序開發(fā)程序中的代碼調(diào)用自身，通過對一系列輸入?yún)?shù)運行相同的操作來計算輸出。所涵蓋的示例只是其實際應(yīng)用的一小部分。Java 軟件開發(fā)工具包 (SDK) 中的各種搜索和排序算法都使用遞歸，包括深度優(yōu)先搜索、歸并排序和樹遍歷。
這并不是說遞歸是萬能的方法，尤其是在內(nèi)存有限的情況下。在這種情況下，建議使用迭代方法來編寫函數(shù)。這使得解決方案更具可擴(kuò)展性并且不易發(fā)生內(nèi)存溢出。
然而，遞歸使成都小程序開發(fā)的軟件工程師能夠利用函數(shù)式編程的最佳實踐并將它們應(yīng)用于面向?qū)ο蟮木幊潭鴽]有副作用。這是一種更聰明的方法，而不是更難。
