iteration without a loop in python -

the following example "think python" book allen downey. while explaining concept of "memos" in dictionaries, quotes following example.

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 

i expecting code return {0:0, 1:1, 5:5} since don't see iteration compute function each value between 1 , 5. see {0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5} returned when code run (as book says would), can't understand why function computed expression res = fibonacci(n-1) + fibonacci(n-2) n=2, n=3 , n=4.

can please explain me? can't quite explanation in book.

try putting print statements code keep track of state of 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) 

yields

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} 

the first (integer) value value of n. can see, fibonacci(5) called, fibonacci(4), fibonacci(3), fibonacci(2) , on. these calls due python encountering

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

and recursively calling fibonacci(n-1). remember, python evaluates expressions left right. after fibonacci(n-1) returns fibonacci(n-2) called.

to better understand order of recursive function calls use decorator:

import functools  def trace(f):     """this decorator shows how function called.     useful recursive functions."""     indent = ' ' * 2      @functools.wraps(f)     def wrapper(*arg, **kw):         arg_str = ', '.join(             ['{0!r}'.format(a) in arg]             + ['{0} = {1!r}'.format(key, val) 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) 

which yields

--> 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} 

you can tell level of indentation each recursive call coming from.