在纸上追踪递归函数

Question

我现在正在学习递归,正如俗话所说,精通递归的最佳方法是尽可能多地练习.我习惯用纸张追踪程序(我猜我们所有人都曾在某些时候).

例如,如果我有一个从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)

Answer 1

把答案放在这里.在我的开发中,我经常使用调试器,他们也帮助了我很多.因此,我建议这样做,因为它们通常比在递归深度上打印字符串更有帮助.

当我想跟踪一个递归函数时我会做什么(这里只是写了一个递归的答案),就是我将断点设置为特定点.

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

我通常做的是创建一个对我很重要的变量的监视列表.我当时所做的是创建一个函数调用图.例如,与在此网站上创建的图表非常相似.

处理递归的最佳方法是使用捆绑了笔和纸的调试器.或者,如果您的调试器支持静态监视列表,那么您有时甚至不需要这样做.但是,我想说在开始时,最好用笔和纸来描绘事物,因为它可以让你更好地理解你的程序是如何工作的.有时候,人们只是使用递归并期望计算机为他们解决问题,然而,这非常棒,你知道你的递归是如何工作的,而且(对于初学者来说)笔和纸是你最好的工具.

Answer 2

以下是我可能会把它放在纸上,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