"""
 memoize2.py

 Demo of memoization using python dictionaries.

 See memoize.py ; this is the same idea implemented differently.

 $ python memoize2.py 
 fibonacci(10) = 89  (11 calls)
 fibonacci(20) = 10946  (10 calls)
 fibonacci(30) = 1346269  (10 calls)

 Jim Mahoney | cs.marlboro.edu | Apr 2012 | MIT License
"""

fibonacci_call_counter = 0

saved_fibonacci = {}

def fibonacci(n):
    global fibonacci_call_counter
    if saved_fibonacci.has_key(n):
        return saved_fibonacci[n]
    else:
        fibonacci_call_counter += 1           # increment global counter
        if n < 2:
            result = 1
        else:
            result = fibonacci(n-1) + fibonacci(n-2)
        saved_fibonacci[n] = result
        return result

def fibonacci_and_count(n):
    global fibonacci_call_counter             #
    fibonacci_call_counter = 0                # reset global counter
    fib = fibonacci(n)
    return (fib, fibonacci_call_counter)

def main():
    for n in (10, 20, 30):
        (fib, count) = fibonacci_and_count(n)
        print " fibonacci(%i) = %i  (%i calls)" % (n, fib, count)

if __name__ == "__main__":
    main()