多遞歸函數

我想指出一個可以更好地解釋函數使用多個遞歸調用時遞歸的引用。我想我知道當一個函數使用單個遞歸實例時，Python如何處理內存。在函數處理數據時，我可以使用打印語句來跟蹤數據在任何給定點的位置。然後，我可以逐步回溯這些步驟，以瞭解如何實現最終的返回值。多遞歸函數

在一次函數調用期間，多次遞歸遞歸實例被觸發時，我不再確定數據是如何被實際處理的。先前照明方式恰當的印刷品陳述揭示了一個看似量子的過程，或者至少更像伏都教。

爲了說明我的困惑，這裏有兩個基本的例子：斐波那契和河內塔的問題。

def getFib(n): 
    if n == 1 or n == 2: 
     return 1 
    return getFib(n-1) + getFib(n-2)

斐波那契示例具有兩個內聯調用。首先是getFib(n-1)解決了整個堆棧，然後getFib(n-2)類似地解決，每個結果被放入新的堆棧，並且這些堆棧逐行添加在一起，這些總和爲總和的結果？

def hanoi(n, s, t, b): 
    assert n > 0 
    if n ==1: 
     print 'move ', s, ' to ', t 
    else: 
     hanoi(n-1,s,b,t) 
     hanoi(1,s,t,b) 
     hanoi(n-1,b,t,s)

河內提出了一個不同的問題，因爲函數調用是連續的行。當函數到達第一個調用時，它是否解析爲n = 1，然後移到第二個已經n = 1的調用，然後是第三個調用，直到n = 1？

再一次，只是尋找參考資料，可以幫助我更好地瞭解引擎蓋下的情況。我相信在這種情況下可能要解釋一下。

來源

2013-10-09 jmike

我認爲第一個函數將永遠與遞歸'N = <0' –

我不明白你的問題。特別是「getFib（n-1）」首先解決了棧中的所有問題，然後同樣解決了「getFib（n-2）」，每個結果都被放入新的堆棧中，並且這些堆棧按行相加那麼這些總和就是爲了結果？「這是什麼意思？評估'getFib（n-1）'，這意味着解釋器執行所有的代碼直到它接收到它的返回值。該代碼碰巧包含對'getFib'的其他調用。 – Bakuriu

http://www.pythontutor.com/visualize.html

甚至還有一個鏈接河內有那麼你可以遵循的代碼流。

這是一個鏈接到他們在他們的網站上顯示的河內代碼，但它可能不得不被用來形象化你的確切代碼。

http://www.pythontutor.com/visualize.html#code=%23+move+a+stack+of+n+disks+from+stack+a+to+stack+b,%0A%23+using+tmp+as+a+temporary+stack%0Adef+TowerOfHanoi(n,+a,+b,+tmp)%3A%0A++++if+n+%3D%3D+1%3A%0A++++++++b.append(a.pop())%0A++++else%3A%0A++++++++TowerOfHanoi(n-1,+a,+tmp,+b)%0A++++++++b.append(a.pop())%0A++++++++TowerOfHanoi(n-1,+tmp,+b,+a)%0A++++++++%0Astack1+%3D+%5B4,3,2,1%5D%0Astack2+%3D+%5B%5D%0Astack3+%3D+%5B%5D%0A++++++%0A%23+transfer+stack1+to+stack3+using+Tower+of+Hanoi+rules%0ATowerOfHanoi(len(stack1),+stack1,+stack3,+stack2)&mode=display&cumulative=false&heapPrimitives=false&drawParentPointers=false&textReferences=false&showOnlyOutputs=false&py=2&curInstr=0

來源

2013-10-09 20:20:04 Garth5689

它可能是我，但似乎沒有幫助。 :) –

感謝加思，視覺表示非常有幫助。 – jmike

是的，它並不適用於所有人，但它確實會同時向您展示堆棧和所有內容。只是另一種看待它的方式。 – Garth5689

回答

相關問題