# 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)