Итерация без цикла в python

Question

Следующий пример из книги «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

Как вы видите, fibonacci является рекурсивной функцией, что означает, что он вызывает себя внутри функции.

Например, рассмотрите fibonacci(2). 2 не находится в known словарях, поэтому res = fibonacci(1)+fibonacci(0) выполнен. Поскольку 0 и 1 известны, их значения (0 и 1) добавление в res так res=1 так fibonacci(2) = 1 и 2 также добавляют в known словарь, и он идет до достигает 5.

Answer 2

Попробуйте поместить операторы печати в код, чтобы сохранить трек состояния 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} 

первый (целое число) Valu e - значение 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} 

Вы можете сказать по уровню отступа, где каждый рекурсивный вызов приходящий из.