瞭解Python中的遞歸:: confused

-1

我有這段代碼計算範圍到2個數字之間的總和。

def sum(lower, upper): 
    if lower > upper: 
     return 0 
    else: 
     return lower + sum(lower +1, upper) 

print(sum(11, 30))

我想了解每個遞歸調用的值存儲在哪裏。因此，如果低於12並且高於30，那麼存儲在哪裏？

感謝傑森

來源

2017-07-11 Jason Aruni

只是一個評論：'sum'是一個[內建函數]（https://docs.python.org/3/library/functions.html#sum）：你應該選擇一個不同的名字... –

42？這是從哪裏來的？這不是一切的答案。對於那些較低和較高的人，你在任何時候都不會有任何地方。 –

要真正理解這一點，你需要看看調用堆棧是如何工作的。 –

每個遞歸的值存儲在調用棧：

您可以顯示功能的拆卸是這樣的：

def my_sum(lower, upper): 
    if lower > upper: 
     return 0 
    else: 
     return lower + my_sum(lower +1, upper) 

import dis 
dis.dis(my_sum)

你得到：

2   0 LOAD_FAST    0 (lower) 
       2 LOAD_FAST    1 (upper) 
       4 COMPARE_OP    4 (>) 
       6 POP_JUMP_IF_FALSE  12 

    3   8 LOAD_CONST    1 (0) 
      10 RETURN_VALUE 

    5  >> 12 LOAD_FAST    0 (lower) 
      14 LOAD_GLOBAL    0 (my_sum) 
      16 LOAD_FAST    0 (lower) 
      18 LOAD_CONST    2 (1) 
      20 BINARY_ADD 
      22 LOAD_FAST    1 (upper) 
      24 CALL_FUNCTION   2 
      26 BINARY_ADD 
      28 RETURN_VALUE 
      30 LOAD_CONST    0 (None) 
      32 RETURN_VALUE

LOAD_FAST例程加載值來自函數堆棧。

這與臨時值相同。

來源

2017-07-11 12:14:51

Python和大多數其他語言使用稱爲堆棧的函數調用結構。如果您不熟悉stack data structure，我會建議您閱讀。它會讓你對堆棧的工作有一個很好的理解。我想推薦檢出this tutorial for a detailed explanation。

來源

2017-07-11 12:18:23 loganasherjones

你的代碼不同的命名慣例寫...

def compute(low, high): 
    if low > high: 
     return 0 
    else: 
     return low + compute(low+1, high)

給定一個整數（低），而另一個整數比所述整數（高）時，該代碼就會發現那些之間的總和兩個整數（含），通過遞歸。

例如>>> compute(6, 9)

上面會通過遞歸方式返回30，即每次初始條件不滿足時，函數被再次調用，將1加到低，以便最終滿足條件，並且當它是（低時等於10）遞歸將設置在與示例compute(6, 9)

儘管如此 - 當低= 10，則返回0，以前低爲9，所以在這一點表達return low + compute(low+1, high)將return 9 + 0，現在上到下一個遞歸調用，在9之前低8 - 我們剛剛從前一個調用返回9，所以return 8 + 9，返回17 ...我認爲你明白了，這個過程發生在最初的返回語句之前。把它想象成緊身短褲，然後讓它恢復初始形態。

請注意，如果沒有最終滿足您的第一個條件以及增量返回語句，該函數將無限地返回相同的事物，以致從未滿足if條件，或無限地將1添加到低位。

我希望這會對遞歸有點點亮。

來源

2017-07-11 12:51:55 flevinkelming

我誤讀了第二行......答覆已被編輯。然而，這仍然是一個不正確的陳述 - 我認爲他打算將最初的論點排除在總和之外。 – flevinkelming

我認爲有很多人說「之間」的意思是包容性的。它讓我感到很困惑，但事實就是如此。我懷疑他「打算」什麼。這聽起來像他寫的代碼，我敢肯定他沒有。順便說一句，「計算」也是一個壞名字，因爲它非常通用。我可能會把它稱爲「範圍」（唯一的缺點是它不等於Python的範圍，因爲它包含了上限）。 –

我同意你的意圖，我只是想給他帶來懷疑的好處。我並沒有試圖將注意力集中在命名約定上，因爲我試圖簡化他的遞歸 - 但是你是對的，我應該使用一些不太模糊的東西。謝謝，斯蒂芬。 – flevinkelming

把它想象成一個呼叫中心。一個廣告說他們告訴你可以請求的範圍內的數字總和。

所以你打電話給那裏的人詢問12到30之間的數字。這個人認爲「對我來說這太複雜了」，並且呼叫同一個呼叫中心自己要求從13到30的總和。那第二個人仍然不能直接打電話給中心再打要求總數從14到30.等等。最終有人會收到一個要求31到30的金額的電話，並直接回復「嗯，這是一個空的範圍，當然是零」。然後它全部倒退。所有參與調用堆棧的人員一直在等待他們的答案，現在逐個計算他們自己的結果並將其報告給調用他們的人。所以答覆是「30」（因爲30 + 0），然後是「59」（因爲29 + 30），然後是「87」（因爲28 + 59）等等。最終人你打電話要求12至30，會收到13至30的總和爲387的答案。他們將它添加到12並回復給你「399」。

在這個比喻中，有些人在等待自己的答案時將自己的請求數據放在頭上。在計算機編程中完成這些數據存儲在哪裏？那麼，在call stack。這就是所謂的堆棧，因爲就像您一次構建一堆文件並一次取下一個文件一樣，這些調用是相互重疊並以相反的順序完成的。就像那個呼叫中心一樣，計算機的調用棧的大小也是有限的。當你詢問的呼叫中心範圍大於呼叫中心的人數時，呼叫中心的每個人都會參與你的請求，而最後呼叫的人將無人跟他通話。在這一點上，系統有點崩潰。在計算機中，這被稱爲「堆棧溢出」。就像這個網站一樣。

來源

2017-07-11 14:27:13

瞭解Python中的遞歸:: confused

回答

相關問題