Fibonacci

Iterative: O(n)

Single for loop

a = 0  # starting num
b = 1

for _ in n:
    print(b)
    c = a + b
    a = b
    b = c
    
return b  # b is the second component of the fibonacci

Recursive: O(2^n)

Creates 2^n (b^n where b is the number of child branches) calls to the stack at time, since the recursive call continues traversing until it reaches the base case.

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    
    # recurse until n reaches 1
    return fibonacci(n-2) + fibonacci(n-1)