什麼是遞迴？如何使用它？

學習遞迴的基礎知識，這是程式設計師必備的但有點費心的工具。...

遞迴是一個有趣的程式設計概念，但學習起來有點棘手。遞迴只是指重複自身的東西。如果你想看到一個厚臉皮的遞迴例子，試著在Google上搜索遞迴。您將發現一個復活節彩蛋，其中搜索結果建議是遞迴的。另一方面，如果您想學習如何編寫遞迴函式，請繼續閱讀！

什麼是遞迴函式(a recursive function)？

遞迴函式是一個呼叫自身的函式。實際上，您建立了一個帶有函式的迴圈。可以想象，這些函式很難編寫。您不希望程式碼永遠執行。

與迴圈類似，遞迴函式將由條件控制。一旦滿足條件，函式就停止呼叫自身，從而停止迴圈。這就是如何建立一個呼叫自身而不會永遠執行的函式。

儘管遞迴函式的作用類似於迴圈，但計算機執行它的方式不同。因此，一些演算法在迴圈中效率更高，而另一些演算法則受益於遞迴函式。但是在我們研究如何使用遞迴函式之前，您需要知道如何編寫一個遞迴函式。

如何編寫遞迴函式

所有遞迴函式都具有相同的基本結構：

FUNCTION name IF condition THEN RETURN result ELSE CALL FUNCTION nameEND FUNCTION

上面的示例是用虛擬碼編寫的。它概述了函式的結構，可以應用於任何語言。為了簡單起見，在本文中，我們將集中討論Python。

關於遞迴函式，首先要注意的是，當滿足條件時，函式退出遞迴。這意味著在編寫遞迴函式時，首先要確定何時停止遞迴。

如果不滿足條件，函式將呼叫自身。因此，如果要將資訊傳送到下一個迴圈，則必須將其作為函式中的引數傳送。這可以賦予遞迴函式更多的功能。

相關：什麼是程式設計中的函式？

python中的遞迴函式示例

當您看到遞迴的實際應用時，理解它是如何工作的就容易多了。為了演示它，讓我們編寫一個遞迴函式，返回一個數的階乘。

階乘返回一個數與其前所有整數的乘積。例如，5的階乘是5×4×3×2×1或120。

def factorialFunction(numberToMultiply): if numberToMultiply == 1 : return 1 else : return numberToMultiply * factorialFunction(numberToMultiply - 1) result = factorialFunction(3)print(result)//Outputs: 6

上面的程式將給出結果6，這是數字3的階乘。一開始可能會有點混亂。如果我們一步一步地完成這個計劃會有幫助的。

呼叫函式時，numberToMultiply等於3。
條件不滿足，所以我們進入else條件。
我們的函式返回3*，但隨後暫停。它必須呼叫自身來確定它返回的值的其餘部分。
這次呼叫函式時，numberToMultiply的值等於2。
條件不滿足，所以我們進入else條件。
我們的函式返回2*，但隨後暫停。它必須呼叫自身來確定它返回的值的其餘部分。
再次呼叫該函式。這一次，numberToMultiply的值等於1。
如果符合我們的條件。函式返回1。
步驟6中的函式現在可以將2*1返回到步驟3中的函式。
第三步的函式現在可以返回3*2*1，也就是6。

遞迴是一個棘手的概念。將其視為將一個函式堆疊在另一個函式之上可能會有所幫助。一旦一個函式被最終解析，它就可以將資訊傳送回堆疊，直到所有函式都有了答案。

這實際上就是你的電腦所做的。當您呼叫函式時，它會一直儲存在記憶體中，直到返回為止。這意味著遞迴函式可以使用比迴圈多得多的記憶體。

因此，將迴圈編寫為遞迴函式可能效率不高，但這是練習構造迴圈的好方法。您應該能夠將迴圈編碼為具有類似結果的遞迴函式。

如何將迴圈轉換為遞迴函式的示例

print("Enter an even number:")i = int(input())while (i % 2) != 0 : print("That number is not even. Please enter a new number:") i = int(input())

此迴圈也可以遞迴編寫為：

def recursiveFunction(number) : if (number % 2) == 0 : return number else: print("That number is not even. Please enter a new number:") recursiveFunction(int(input())) print("Enter and even number:")i = recursiveFunction(int(input()))

第一步是確定函式何時停止。在這種情況下，我們希望它在輸入偶數後停止。在我們的示例中，number跟蹤使用者的輸入。如果他們輸入一個偶數，我們就返回這個數。否則，我們將繼續要求一個新號碼。

為了建立迴圈，我們再次呼叫函式。但這一次，我們傳遞給下一個函式的數字是使用者輸入的新數字。下一個函式呼叫將檢查號碼。

這是一個非常糟糕的函式！是的，它正在檢查數字是否是偶數，就像我們的迴圈一樣，但它不是有效的。每次使用者輸入一個奇數時，該函式都儲存在記憶體中，並呼叫一個新函式。如果你這樣做的次數足夠多，你的記憶體就會用完！

相關：幫助您快速學習的基本Python示例

遞迴函式的真實示例

上面的例子是不使用遞迴的好例子。那麼，遞迴在哪裡使用？搜尋二叉樹就是一個很好的例子。

當資料在二叉樹中結構化時，您必須沿著許多路徑來搜尋資料。在樹中的每個點上，您都必須決定是要繼續從右側還是左側進行搜尋。您可以將訪問的樹的哪一部分儲存在變數中，但是遞迴函式可以自然地跟蹤該資訊。

想象一下，我們正在上面的樹上尋找數字6。我們可以做一個遞迴函式，從左到右搜尋樹。演算法如下所示：

FUNCTION searchTree(branchToSearch) IF find 6 OR end of tree THEN RETURN result ELSE PROCESS branch CALL FUNCTION searchTree(left) CALL FUNCTION searchTree(right)END FUNCTION

在這個虛擬碼示例中，演算法將首先搜尋樹的左側。每次訪問一個新號碼時，該功能都會暫停並儲存在記憶體中。這使我們能夠追蹤我們去過的地方。

該演算法總是首先儘可能地搜尋左側。一旦到達樹的末尾，searchTree（左）將完成，它將檢查右側。一旦兩邊都被選中，搜尋將備份一個分支並繼續檢查右側。

如果演算法搜尋整棵樹，它會按以下順序進行：

2、7、2、6、5、11、5、9和4

看看是否可以使用上面的虛擬碼。