title: Tracing the execution of a cached Fibonacci Sequence (using python decorator)
body: <p>Using the common memoization pattern below along w/ a fibonnaci function, I am having some trouble visualizing how it actually works.  I understand the concept but thinking through the program I get confused and start thinking in circles.</p>
  
  <pre><code>def memoize(func):
      cache={}
      def wrapper(*args,**kwargs):
          if args in cache:
              return cache[args]
          else:
              cache[args]=func(*args) #to store the result, doesn't fib still have to go through all it's calculations here?
              return cache[args]
      return wrapper
  
  @memoize
  def fib(n):
      if n==0:
          return 0
      elif n==1:
          return 1
      else:
          return fib(n-2)+fib(n-1)
  </code></pre>
  
  <p>So conceptually I understand how recursion works, and I understand the idea behind memoization (first try to look it up to avoid running the same calc multiple times).  What confuses me though, is when you are adding a key to the dictionary for a function call who's arguments have not yet been seen, how that can be done without going through the full function call. </p>
  
  <p>For example, if we call fib(5) then when we hit <code>cache[args]=func(*args)</code>we add a <code>key:value</code> pair of <code>5:fib(5)</code> to the dictionary (since 5 has not yet been seen).  But the <code>v</code> in that <code>k:v</code> pair is the function call to of fib(5) which still needs to return it's value, and I would think that requires going through the entire recursion process.  If we are trying to cache the return value, how does the memoization get this return value for fib(5) without going through the entire recursion process?</p>