python - python中没有循环的迭代

Question

以下示例来自 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。

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

Answer 1

尝试将打印语句放入代码中以跟踪已知的状态:

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) 是调用，然后是 fibonacci(4)，然后是 fibonacci(3)，然后是 fibonacci(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}

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