in mathematics the fibonacci numbers commonly denoted fn form a sequence called the fibonacci sequence such that each number is the sum of the two preceding ones starting from 0 and 1 that is f00 f11 and fn fn1 fn2 the fibonacci numbers are the numbers in the following integer sequence 0 1 1 2 3 5 8 13 21 34 55 89 144 in mathematical terms the sequence fn of fibonacci numbers is defined by the recurrence relation here given a number n print nth fibonacci number summary computes the nth fibonacci number recursive problem this implementation is very slow approximate o2n arguments n int description returns int description precondition printfibrecursive35 9227465 slow summary this algorithm computes the nth fibbonacci number very quick approximate on the algorithm use dynamic programming arguments n int description returns int description precondition printfiblist100 354224848179261915075 summary works iterative approximate on arguments n int description returns int description precondition printfibiter100 354224848179261915075 summary computes the n th fibonacci number recursive problem this implementation is very slow approximate o 2 n arguments n int description returns int description precondition print fib_recursive 35 9227465 slow summary this algorithm computes the n th fibbonacci number very quick approximate o n the algorithm use dynamic programming arguments n int description returns int description precondition print fib_list 100 354224848179261915075 summary works iterative approximate o n arguments n int description returns int description precondition print fib_iter 100 354224848179261915075
def fib_recursive(n):
    

    
    assert n >= 0, 'n must be a positive integer'

    if n <= 1:
        return n
    return fib_recursive(n-1) + fib_recursive(n-2)




def fib_list(n):
    

    
    assert n >= 0, 'n must be a positive integer'

    list_results = [0, 1]
    for i in range(2, n+1):
        list_results.append(list_results[i-1] + list_results[i-2])
    return list_results[n]




def fib_iter(n):
    

    
    assert n >= 0, 'n must be positive integer'

    fib_1 = 0
    fib_2 = 1
    res = 0
    if n <= 1:
        return n
    for _ in range(n-1):
        res = fib_1 + fib_2
        fib_1 = fib_2
        fib_2 = res
    return res