# Jay Summet, CS 1301, Donated to the public domain Nov 2008.
#Fibonacci example, recursive (with cache) and iterative.
fibCache = {}
def fib(N):
global fibCache
if (N == 0):
return(0)
if (N == 1):
return (1)
result = fibCache.get(N, -1)
#If the result is already in the cache, return it
if( result != -1):
return(result)
else: #otherwise, calculate it, and place answer in cache.
result = fib(N-1) + fib(N-2)
fibCache[N] = result
return(result)
#Iterative version. (Does not require a cache for single use, but
# would benefit from one for multiple uses.)
def iFib(N):
if (N == 0):
return(0)
if (N == 1):
return (1)
#N => 2
lastOne = 1
secondToLastOne = 0
for i in range(2,N+1):
result = lastOne + secondToLastOne
secondToLastOne = lastOne
lastOne = result
return(result)