Skip to main content
 首页 » 编程设计

python之多重递归函数

2024年11月01日8傻小

当一个函数使用多个递归调用时,我希望被指向一个可以更好地解释递归的引用。我想我明白了当函数使用单个递归实例时 Python 是如何处理内存的。在函数处理数据时,我可以使用 print 语句来跟踪数据在任何给定点的位置。然后,我可以将这些步骤中的每一步都往回走,看看最终的返回值是如何实现的。

一旦在单个函数调用期间触发了多个递归实例,我就不再确定数据实际上是如何处理的。之前在适当位置打印语句的启发性方法揭示了一个看起来是量子的过程,或者至少更像巫术。

为了说明我的困惑,这里有两个基本示例:斐波那契和汉诺塔问题。

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

Fibonacci 示例具有两个内联调用。 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) 

Hanoi 提出了一个不同的问题,因为函数调用是连续的。当函数到达第一个调用时,它是否将其解析为 n=1,然后转到已经是 n=1 的第二个调用,然后转到第三个直到 n=1?

同样,我只是在寻找可以帮助我了解这里发生的事情的引用资料。我敢肯定,在这种情况下解释起来可能有点多。

请您参考如下方法:

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

那里甚至还有一个 Hanoi 链接,因此您可以跟随代码流。

这是他们在其网站上显示的 hanoi 代码的链接,但可能需要对其进行修改以显示您的确切代码。

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