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