cache = {}

 function fib(n):
   if n in cache:
      return cache[n]     # skip work already done
   if n <= 1:
      result = n
   else:

      result = fib(n - 1) + fib(n - 2)
   cache[n] = result
   return result          # O(n) instead of exponential
