Python 遞歸函數概念：Python 初學者教程

在計算機科學的世界中，遞歸是指用自己的術語定義事物的技術。 換句話說，遞歸函數調用自身進行處理。 在本文中，我們將了解Python 中遞歸函數的概念，這是一種 21 世紀廣泛使用的編程語言。

什麼是Python 遞歸？

在 Python 中，一組執行特定任務的相關語句稱為“函數”。 因此，函數將您的程序分成更小的塊。 眾所周知，一個函數可以在 Python 中調用其他函數。

但是其他一些函數可以調用自己。 這些被稱為遞歸函數。 考慮兩個相互面對放置的平行鏡子。 現在，保留在鏡子之間的任何物體都將被遞歸反射。

讓我們詳細了解遞歸函數以清楚地了解它的工作原理。

遞歸函數

我們知道Python 中的遞歸函數調用自身，因為它是通過自引用表達式定義的，即根據自身。 它不斷重複其行為，直到滿足特定條件以返回值或結果。 現在讓我們看一個例子來了解它是如何工作的。

另請閱讀： Python 面試問答

假設你想找出一個整數的階乘。 階乘只不過是所有數字的乘積，從 1 到該整數。 例如，5 的階乘（寫成 5！）將是 1*2*3*4*5*6，即 720。我們有一個遞歸函數 calc_factorial(x)，定義如下：

def calc_factorial(x):

#遞歸函數求整數的階乘

如果 x == 1：

返回 1

別的

返回 (x * calc_factorial(x-1))

如果你用一個像 4 這樣的正整數調用這個函數會發生什麼？ 好吧，每個函數調用都會添加一個堆棧幀，直到我們達到基本情況（當數字減少到 1 時）。 需要基本條件，以便遞歸結束並且不會無限期地繼續。 因此，在給定的情況下，值 24 將在第四次調用後返回。

Python中遞歸函數的實現

Python中遞歸函數可以有多種應用。 例如，您想製作具有重複圖案的圖形，例如 Koch 雪花。 遞歸可用於生成分形圖案，這些圖案由相同設計的較小版本組成。

另一個例子是遊戲解決。 您可以編寫遞歸算法來解決數獨和許多複雜的遊戲。 遞歸最常用於搜索、排序和遍歷問題。

該函數的一個顯著特點是遞歸實現允許回溯。 因此，遞歸就是逐步構建解決方案並刪除那些在任何階段都不滿足問題約束的解決方案。 實現這一點需要兩件事——維護狀態和合適的數據結構。 請繼續閱讀以熟悉這些術語。

閱讀：印度的 Python 開發人員薪水

維持狀態

Python 中的每個遞歸調用都有自己的執行上下文。 在 Python 中處理遞歸函數時，您必須通過每個遞歸調用線程化狀態。 這樣，當前狀態就成為當前調用執行上下文的一部分。 您還可以將狀態保持在全局範圍內。

例如，如果您使用遞歸來計算 1+2+3+4+…….+10。 在這裡，您添加的當前數字和累積到該點的總和形成您需要維護的狀態。 維護狀態涉及通過每次調用將更新的當前狀態作為參數傳遞。 這是你如何做到的。

def sum_numbers（current_number，accumulated_sum）

＃基本情況

#返回最終狀態

如果當前數字==11：

返回累積的和

#遞歸案例

#通過遞歸調用線程化狀態

別的：

返回 sum_numbers（current_number + 1，accumulated_sum + current_number）

或者，您可以使用全局可變狀態。 要使用此方法維護狀態，請將狀態保持在全局範圍內。

current_number = 1

累積總和 = 0

def sum_numbers():

全球 current_number

全局累計和

＃基本情況

如果 current_number==11

返回累積的和

#遞歸案例

別的：

累計總和 = 累計總和 + 當前數

當前編號 = 當前編號 + 1

返回 sum_numbers()

遞歸數據結構

如果可以根據自身的更小和更簡單的版本來定義數據結構，則認為它是遞歸的。 遞歸數據結構的示例包括列表、樹、層次結構、字典等。列表可以有其他列表作為元素。 一棵樹有子樹、葉子節點等等。

在這裡需要注意的是，遞歸函數的結構通常是在它作為輸入的數據結構之後建模的。 因此，遞歸數據結構和遞歸函數齊頭並進。

斐波那契計算中的遞歸

意大利數學家斐波那契在 13 世紀首先定義了斐波那契數，以模擬兔子的種群增長。 他推斷，從第一年的一對兔子開始，某一年出生的兔子對數等於最近兩年每年出生的兔子對數。 這可以寫成：Fn = Fn-1 + Fn-2（基本情況：F0=1 和 F1=1）。

當你編寫一個遞歸函數來計算斐波那契數時，它可能會導致簡單的遞歸。 當遞歸函數的定義被天真地遵循時，就會發生這種情況，並且您最終會不必要地重新計算值。 為避免重新計算，您可以將 lru_cache 裝飾器應用於函數。 它緩存結果並避免過程變得低效。

閱讀更多：每個 Python 開發人員都應該知道的 10 大 Python 工具

遞歸的優缺點

遞歸通過將復雜任務拆分為子問題來幫助簡化它。 遞歸函數使代碼更簡潔，序列生成也不復雜。 但遞歸併非沒有局限性。 有時，調用可能會耗費大量時間和內存，因此代價高昂且效率低下。 遞歸函數也可能難以調試。

包起來

在本文中，我們介紹了Python 遞歸的概念，並通過一些示例對其進行了演示，並討論了它的一些優點和缺點。 有了所有這些信息，你就可以在下一次 Python 面試中輕鬆解釋遞歸函數了！

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