For all those stupid fibonnaci questions

fib.py

def fib_n_recur(n):
    ''' Recursive fibonnaci 
    
    Pro: Matches mathematical definition
    Con: O(2^n) runtime; n > 40 crazy slow; will blow the stack on large n
    '''
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib_n_recur(n - 1) + fib_n_recur(n - 2)

def fib_n_recur_memo(n, memo=None):
    ''' Recursive fibonnaci with Memoization
    
    Pro: Runtime improved at cost of memory
    Con: Blows the stack around n > 2503
    '''
    if memo is None:
        memo = {0: 0, 1: 1}

    if n in memo:
        return memo[n]
    
    memo[n] = fib_n_recur_memo(n - 1, memo) + fib_n_recur_memo(n - 2, memo) 
    return memo[n]


def fib_n_iter(n):
    ''' Iterative fibonnaci 
    
    Pro: Good runtime O(n); handle large n's without inaccuracy or blowing stack
    Con: Complicated and easy to screw up
    '''
    if n == 0:
        return 0
    elif n == 1:
        return 1

    current, nxt, count = 0, 1, 0
    while count < n:
        temp = current + nxt
        current = nxt
        nxt = temp
        count += 1
    return current
        

from math import sqrt

def fib_n_math(n):
    ''' Mathematical fibonnaci

    Pro: Fastest
    Con: Inaccurate at n > 71; requires special knowledge to write/update
    '''
    numerator = (1 + sqrt(5))**n - (1 - sqrt(5))**n
    denominator = 2**n * sqrt(5)
    return int(numerator / denominator)