# 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