6

我现在正在学习递归，俗话说，精通递归的最好方法是尽可能多地练习。我有在纸上跟踪程序的习惯（我想我们所有人都曾有过）。

例如，如果我有一个功能，比如打印一个从 1 到 10 的数字：

def print_n():
    for i in range(1,11):
        print i

我会像这样追踪：

i
.......
1
2
3
4
... and so on

但是当我练习递归时，我发现很难在纸上跟踪程序。有人可以举个例子推荐一种在纸上跟踪递归函数的最佳方法吗？您可以使用以下斐波那契（再次！！！）来说明您的示例，否则您可能会让读者感到惊讶。

#RECURSIVE FUNCTION TO RETURN Nth FIBONACCI NUMBER
def fib(n):
    if n is 0 or n is 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)
4

4 回答 4

8

只是把这个答案扔在这里。在我的开发过程中，我经常使用调试器，它们也给了我很多帮助。所以，我推荐这个，因为它们通常比仅仅在递归深度上打印出字符串更有帮助。

当我想跟踪一个递归函数（只是在这里写了一个递归答案）时，我会做的是我将断点设置为特定点。

理想情况下，大多数调试器将允许您查看与当前范围相关的值列表，并允许您step into调用函数以查看其运行方式。

我通常做的是创建一个对我很重要的变量的监视列表。然后我要做的是创建一个函数调用图。例如，与在本网站上创建的图表非常相似。

在此处输入图像描述

我处理递归的最佳方法是使用与笔和纸捆绑在一起的调试器。或者，如果您的调试器支持静态监视列表，那么您有时甚至不需要这样做。但是，我想说，在开始时，最好用笔和纸勾勒出来，因为它可以让您更好地了解您的程序是如何工作的。有时，人们只是使用递归并期望计算机为他们解决问题，这太棒了，但是，你必须知道递归是如何工作的，为此（对于初学者）笔和纸是你最好的工具。

于 2013-10-29T20:17:14.620 回答
6

以下是我可能会将其写在纸上的方式，fib(5)如下所示：

                                          fib(5)
                       fib(4)               +                  fib(3)
              fib(3)     +      fib(2)      +         fib(2)     +   fib(1)   
     fib(2)     + fib(1) + fib(1) + fib(0)  +    fib(1) + fib(0) +     1
fib(1) + fib(0) +   1    +   1    +   1     +      1    +   1    +     1
  1    +   1    +   1    +   1    +   1     +      1    +   1    +     1
于 2013-10-29T20:17:07.097 回答
4

让电脑为您完成繁重的工作！通过添加几行，您可以看到函数如何递归地潜入：

def fib(n,depth=0):
    print ''.join(["*"]*depth), n

    if n is 0 or n is 1:
        return 1
    else:
        return fib(n-1,depth+1) + fib(n-2,depth+1)

fib(5)

给出：

 5
* 4
** 3
*** 2
**** 1
**** 0
*** 1
** 2
*** 1
*** 0
* 3
** 2
*** 1
*** 0
** 1

请注意，我们正在跟踪除了n现在之外的深度。在这种情况下，很容易看出它们之间是如何depth相关n的，但在其他情况下，它可能不那么明显，所以这个练习并不完全是学术性的。depth我们通过线打印出一个视觉表示，''.join(["*"]*depth)它简单地创建一个具有*相同深度大小的字符串。

于 2013-10-29T20:03:45.990 回答
4

它会是这样的：

fib(3)
 n=3 so return fib(2) + fib(1)

So now we need fib(2) and fib (1)

   fib(2)
    n =2 so return fib(1)+fib(0)
    fib (1)
     n=1 so return 1

    fib (0) 
     n=0 so return 1

    Now we can have fib(2) return 1+1 = 2. We still need to do fib(1) to return the value of fib(3)

    fib(1)
     n=1 so return 1

Now we can return fib(3)'s value of 2+1=3
于 2013-10-29T20:07:59.827 回答