1

以下示例来自 Allen Downey 的“Think Python”一书。在解释字典中“备忘录”的概念时，他引用了下面的例子。

known = {0:0, 1:1}
def fibonacci(n):
    if n in known:
        return known[n]
    res = fibonacci(n-1) + fibonacci(n-2)
    known[n] = res
    return res
fibonacci(5)
print known

我期待这段代码返回{0:0, 1:1, 5:5}，因为我没有看到任何迭代来计算 1 到 5 之间的每个值的函数。但是{0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5}当代码运行时，我看到的会返回（正如书中所说），但我可以'不明白为什么函数计算res = fibonacci(n-1) + fibonacci(n-2)n=2、n=3 和 n=4 的表达式。

有人可以向我解释一下吗？书里的解释我不太明白。

4

2 回答 2

4

尝试将打印语句放入代码中以跟踪状态known：

def fibonacci(n):
    print(n, known)
    if n in known:
        return known[n]
    res = fibonacci(n-1) + fibonacci(n-2)

    known[n] = res
    return res
fibonacci(5)
print(known)

产量

5 {0: 0, 1: 1}
4 {0: 0, 1: 1}
3 {0: 0, 1: 1}
2 {0: 0, 1: 1}
1 {0: 0, 1: 1}
0 {0: 0, 1: 1}
1 {0: 0, 1: 1, 2: 1}
2 {0: 0, 1: 1, 2: 1, 3: 2}
3 {0: 0, 1: 1, 2: 1, 3: 2, 4: 3}
{0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5}

第一个（整数）值是 的值n。如您所见，fibonacci(5)被称为 then fibonacci(4)、 then fibonacci(3)、 thenfibonacci(2)等等。这些调用都是由于Python遇到

    res = fibonacci(n-1) + fibonacci(n-2)

并递归调用fibonacci(n-1). 请记住，Python 从左到右计算表达式。所以只有在 调用fibonacci(n-1)返回之后。fibonacci(n-2)

为了更好地理解递归函数调用的顺序，你可以使用这个装饰器：

import functools

def trace(f):
    """This decorator shows how the function was called.
    Especially useful with recursive functions."""
    indent = ' ' * 2

    @functools.wraps(f)
    def wrapper(*arg, **kw):
        arg_str = ', '.join(
            ['{0!r}'.format(a) for a in arg]
            + ['{0} = {1!r}'.format(key, val) for key, val in kw.items()])
        function_call = '{n}({a})'.format(n=f.__name__, a=arg_str)
        print("{i}--> {c}".format(
            i=indent * (trace.level), c=function_call))
        trace.level += 1
        try:
            result = f(*arg, **kw)
            print("{i}<-- {c} returns {r}".format(
                i=indent * (trace.level - 1), c=function_call, r=result))
        finally:
            trace.level -= 1
        return result
    trace.level = 0
    return wrapper

known = {0:0, 1:1}
@trace
def fibonacci(n):
    # print(n, known)
    if n in known:
        return known[n]
    res = fibonacci(n-1) + fibonacci(n-2)

    known[n] = res
    return res
fibonacci(5)
print(known)

产生

--> fibonacci(5)                         
  --> fibonacci(4)                        # fibonacci(5) calls fibonacci(4)
    --> fibonacci(3)                      # fibonacci(4) calls fibonacci(3)
      --> fibonacci(2)                    # fibonacci(3) calls fibonacci(2)
        --> fibonacci(1)                  # fibonacci(2) calls fibonacci(1)
        <-- fibonacci(1) returns 1
        --> fibonacci(0)                  # fibonacci(2) calls fibonacci(0)
        <-- fibonacci(0) returns 0
      <-- fibonacci(2) returns 1
      --> fibonacci(1)                    # fibonacci(3) calls fibonacci(1)
      <-- fibonacci(1) returns 1
    <-- fibonacci(3) returns 2
    --> fibonacci(2)                      # fibonacci(4) calls fibonacci(2) 
    <-- fibonacci(2) returns 1
  <-- fibonacci(4) returns 3
  --> fibonacci(3)                        # fibonacci(5) calls fibonacci(3) 
  <-- fibonacci(3) returns 2
<-- fibonacci(5) returns 5
{0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5}

您可以通过每个递归调用来自的缩进级别来判断。

于 2016-01-16T22:53:03.320 回答
0

如您所见fibonacci，这是一个递归函数，这意味着它在函数内部调用自身。

例如考虑fibonacci(2). 2不在known字典中，所以res = fibonacci(1)+fibonacci(0)被执行。因为0和1是已知的，它们的值（0 和 1）添加到resso和 2 中也添加到字典中res=1，直到达到 5。fibonacci(2) = 1known

于 2016-01-16T22:36:36.330 回答