# Jay Summet, CS 1301, Donated to the public domain June 2014.
# Fibonacci examples, recursive (no cache), recursive (with cache) and iterative.
#Recursive solution
def recFib(N):
#Base Cases
if (N == 0):
return 1
if (N == 1):
return 1
#Recursive case
ans = recFib(N-1) + recFib(N-2)
return ans
#Recursive Solution with a cache, prefilled with base cases!
fibCache = {0:1, 1:1 }
def fib(N):
global fibCache
#If the answer is in the cache (like the base cases, or already computed work)
#just return it!
if N in fibCache
return fibCache[N]
else: #Calculate the answer, and place it in the cache!
ans = fib(N-1) + fib(N-2)
fibCache[N] = ans
return ans
#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 1
if N == 1:
return 1
#N => 2
lastOne = 1
secondToLastOne = 1
for i in range(2,N+1):
result = lastOne + secondToLastOne
secondToLastOne = lastOne
lastOne = result
return result