數據結構中的遞歸：它是如何工作的、類型以及何時使用

讓我們從數據結構中遞歸的定義開始。 稍後我們將討論不同類型的遞歸以及如何使用遞歸來解決不同的問題。

什麼是遞歸？

簡而言之，遞歸是一種解決問題的方法，在某些情況下，它是一種具有非常特殊和專有屬性的編程技術。 在遞歸中，函數或方法具有調用自身來解決問題的能力。 遞歸過程涉及通過將問題轉化為自身的較小變體來解決問題。

函數調用自身的過程可以直接發生，也可以間接發生。 這種調用的不同導致了不同類型的遞歸，我們稍後會討論。 可以使用遞歸解決的一些問題包括圖的 DFS、河內塔、不同類型的樹遍歷等。 要了解遞歸和其他數據科學概念，請查看 IIIT-B 的數據科學在線課程。

閱讀： 13 個有趣的數據結構項目理念

遞歸是如何工作的？

遞歸的概念建立在這樣一種思想上，即如果問題以一個或更小的版本表示，則可以很容易地在更短的時間內解決問題。 添加基本​​條件以停止遞歸是使用此算法解決問題的另一個重要部分。

人們通常認為不可能根據自身來定義實體。 遞歸證明該理論是錯誤的。 如果這項技術以正確的方式進行，它可能會產生非常強大的結果。 讓我們通過幾個例子來看看遞歸是如何工作的。 什麼是句子？ 它可以定義為在連詞的幫助下將兩個或多個句子連接在一起。 類似地，文件夾可以是用於存儲文件和文件夾的存儲設備。 祖先可以是家譜中一個家庭成員的父母和另一個家庭成員的祖先。

遞歸有助於使用一些非常簡單的詞來定義復雜的情況。 您通常如何定義祖先？ 父母、祖父母或曾祖父母。 這可以繼續下去。 同樣，定義文件夾可能是一項艱鉅的任務。 它可以是任何包含一些文件和文件夾的東西，這些文件和文件夾本身可能是文件和文件夾，並且可以再次繼續。 這就是為什麼遞歸使定義情況比平常容易得多的原因。

遞歸也是一種足夠好的編程技術。 遞歸子程序被定義為直接或間接調用自身的子程序。 調用子程序直接表示子程序的定義已經有了調用已定義子程序的調用語句。

另一方面，子程序的間接調用發生在一個子程序調用另一個子程序時，而另一個子程序又調用了原來的子程序。 遞歸可以用幾行代碼來描述一個非常複雜的任務。 現在讓我們將注意力轉向我們已經觸及的不同類型的遞歸。

另請閱讀：要學習的前 6 種編程語言

遞歸的類型

正如已經提到的，只有兩種類型的遞歸。 讓我們看看它們之間有何不同。 直接遞歸是更簡單的方法，因為它只涉及調用原始函數或方法或子例程的單個步驟。 另一方面，間接遞歸涉及幾個步驟。

第一次調用由原始方法對第二個方法進行，後者又調用原始方法。 這個調用鏈可以包含許多方法或函數。 簡單來說，我們可以說間接遞歸的深度總是存在變化的，而這種深度的變化取決於過程中涉及的方法的數量。

直接遞歸可用於單獨調用單個函數。 另一方面，間接遞歸可用於在其他函數的幫助下調用多個方法或函數，並且多次調用。 間接遞歸不會產生開銷，而其直接對應物會產生開銷。

什麼時候使用遞歸？

在某些情況下，您可以使用遞歸或迭代。 但是，您應該始終選擇看起來更適合問題的解決方案。 當涉及到數據抽象時，遞歸總是一個合適的選擇。 人們經常使用遞歸定義來定義數據和相關操作。

可以說遞歸主要是解決與對數據執行不同操作相關的問題的自然解決方案也不會錯。 但是，與遞歸相關的某些事情可能不會使其成為每個問題的最佳解決方案。 在這些情況下，像迭代方法這樣的替代方法是最合適的。

遞歸的實現使用了大量的堆棧空間，這通常會導致冗餘。 每次使用遞歸時，我們都會調用一個方法，從而創建該方法的新實例。 這個新實例攜帶不同的參數和變量，它們存儲在堆棧中，並在返回時獲取。 因此，雖然遞歸是比其他解決方案更簡單的解決方案，但它通常不是最實用的。

此外，我們沒有一組預定義的規則可以幫助為不同的問題選擇迭代或遞歸。 使用遞歸的最大好處是它是一種簡潔的方法。 這使得閱讀和維護它比平時更容易。 但是遞歸方法並不是我們可用的最有效的方法，因為它們佔用大量存儲空間並在實現過程中消耗大量時間。

記住一些事情可以幫助您決定為問題選擇遞歸是否是正確的方法。 如果您要解決的問題以遞歸方式提及並且遞歸解決方案似乎不那麼複雜，您應該選擇遞歸。

您應該知道，在大多數情況下，遞歸簡化了您要使用的算法的實現。 現在，如果與使用迭代和遞歸相關的複雜性對於給定的問題是相同的，那麼您應該使用迭代，因為它更有效的機會更高。

另請查看： 23 門最佳計算機編程課程，以找到工作

結論

但是，在某些情況下，做出決定可能並不那麼容易。 您必須在效率和簡單性之間做出選擇。 如果您是一位經驗豐富的設計師，您將確切地知道何時更重視效率，何時選擇簡單或簡潔而不是它是要走的路。

如果您想了解數據結構、數據科學，請查看 IIIT-B 和 upGrad 的數據科學執行 PG 計劃，該計劃專為在職專業人士創建，提供 10 多個案例研究和項目、實用的實踐研討會、行業指導專家，與行業導師一對一，400 多個小時的學習和頂級公司的工作協助。