"""This module implements two equivalent fibonacci-functions
Both functions compute the fibonacci numbers, but the second one is by far
faster ... The versions here have counters for the calls of
the function and lookups in the memo-dictionary.
"""
def fib(n):
"Return the fibonacci number of n."
global _calls
_calls += 1
if n <= 1:
return n
else:
return fib(n-1) + fib(n-2)
_fib_mem = {}
def fib_memo(n):
"""Return the fibonacci number of n."""
global _calls
global _lookups
_calls += 1
if n <= 1:
return n
elif n in _fib_mem: # Check whether we have already calculated the
# fibonacci number of n
_lookups += 1
return _fib_mem[n]
else:
res = fib_memo(n-1) + fib_memo(n-2)
_fib_mem[n] = res
return res
if __name__ == "__main__":
for n in range(2, 11):
_calls = 0
fib(n)
print("fib(%s): fib has been called %s times" % (n, _calls))
for n in range(2, 11):
_calls = 0
_lookups = 0
_fib_mem = {}
fib_memo(n)
print("fib_memo(%s): fib_memo called %s times (with %s lookups)" %
(n, _calls, _lookups))