多递归函数

我想指出一个可以更好地解释函数使用多个递归调用时递归的引用。我想我知道当一个函数使用单个递归实例时，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

回答

相关问题