# Jay Summet, CS 1301, Donated to the public domain June 2009.
# Fibonacci examples, recursive (no cache), recursive (with cache) and iterative.
#Recursive solution
def recFib(N):
if (N == 0):
return 0
if (N == 1):
return 1
return ( recFib(N-1) + recFib(N-2) )
#Recursive Solution with a cache
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)