fibonacciCache = {} # Create the global cache.
def fibonacci(nthNumber, indent=0):
global fibonacciCache
indentation = '.' * indent
print(indentation + 'fibonacci(%s) called.' % (nthNumber))
if nthNumber in fibonacciCache:
# If the value was already cached, return it.
print(indentation + 'Returning memoized result: %s' % (fibonacciCache[nthNumber]))
return fibonacciCache[nthNumber]
if nthNumber == 1 or nthNumber == 2:
# BASE CASE
print(indentation + 'Base case fibonacci(%s) returning 1.' % (nthNumber))
fibonacciCache[nthNumber] = 1 # Update the cache.
return 1
else:
# RECURSIVE CASE
print(indentation + 'Calling fibonacci(%s) (nthNumber - 1).' % (nthNumber - 1))
result = fibonacci(nthNumber - 1, indent=indent + 1)
print(indentation + 'Calling fibonacci(%s) (nthNumber - 2).' % (nthNumber - 2))
result = result + fibonacci(nthNumber - 2, indent=indent + 1)
print('Call to fibonacci(%s) returning %s.' % (nthNumber, result))
fibonacciCache[nthNumber] = result # Update the cache.
return result
print(fibonacci(10))
print(fibonacci(10))