返回函數如何在遞歸中工作？

Question

我不明白return語句如何在任何遞歸函數中工作（在python中）。有人可以給我一些基本的例子，說明發生了什麼，當你在遞歸函數中返回「東西」時？

Answer 1

遞歸是一種優雅的編程風格，其中函數以更簡單的形式調用自身，直到實現最簡單的形式。

這個最簡單的形式被稱爲'基本情況'（在下面的例子中，基本情況是if n == 1: return 1，因爲對於階乘，1是最簡單的情況下，你需要達到）這是一個測試，看看是否輸入處於最簡單的狀態。

一個遞歸函數的另一部分是「遞歸情況下」，其進一步簡化了功能（在以下例子中，n * factorial(n-1)是遞歸情況下，因爲它是使用簡化的n-1功能）。

一個簡單的，遞歸階乘函數：

def factorial(n): # only works for positive numbers 
    if n == 1: return 1 # base case 
    return n * factorial(n-1) # recursive case; only executed if the above is not 
           # executed because 'return' stops a function 

階乘是所有數字的直至幷包括n乘法。

我們把這個分開： factorial(4)：

1. 是n 1？沒有，所以return n * factorial(n-1)
2. 4 * factorial(4-1) = 4 * factorial(3)
3. 是n 1？沒有，所以return n * factorial(n-1)
4. 3 * factorial(3-1) = 3 * factorial(2)
5. 是n 1？沒有，所以return n * factorial(n-1)
6. 2 * factorial(2-1) = 2 * factorial(1)
7. 是n 1？是的，所以return 1

現在讓我們跟蹤調用：

步驟1，3，5只是檢查，所以他們真的不返回任何東西：

• 第2步：factorial(4) = 4 * factorial(3)
• 步驟4：factorial(3) = 3 * factorial(2)
• 步驟6：factorial(2) = 2 * factorial(1)
• 步驟7：factorial(1) = 1。

因此，跟蹤return語句： 1 * 2 * 3 * 4 = 24，其是4

Answer 2

階乘當一個函數使得遞歸調用，則控制傳遞到被叫功能。當函數返回時，控制將的傳遞給調用該函數的那個​​函數。這是一個交互式調試器如何描述發生了什麼：步驟在到一個函數，步驟在每個語句，步驟出的功能。

函數調用的通常簿記是稱爲堆棧的結構。我們應該想象一堆放在彈簧上的盤子。函數的每個調用（調用）都是一個「推」到棧頂的「板塊」。每個從函數返回的「彈出」調用離開堆棧。

Answer 3

下面是一個使用縮進表示遞歸調用（通過測量堆棧的深度）

>>> import inspect 
>>> def factorial(n): 
...  print('{:{}}factorial({})'.format('', len(inspect.stack()), n)) 
...  retval = 1 if n == 1 else n * factorial(n-1) 
...  print('{:{}}return {}'.format('', len(inspect.stack()), retval)) 
...  return retval 
... 
>>> factorial(5) 
    factorial(5) 
    factorial(4) 
    factorial(3) 
    factorial(2) 
     factorial(1) 
     return 1 
    return 2 
    return 6 
    return 24 
    return 120 
120