Here are 3 implementations of the fibonacci function explained

Iteration:

the iterative solution is probably what comes to mind first.

## an iterative solution
def fib_simple(n):
    nums = [0,1] # start with 0 and 1 as first two terms
    for i in range(n-1):
        ## sum the last and second last num in nums and append
        nums.append(nums[-2] + nums[-1])
        
    return nums[n] ## return the last num in nums

Recursion:

Explanation:

say n = 5, we can observe fib(5):

fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)
fib(1) & fib(2) = 1

## fib function implemented with recursion
def fib_recursion(n):
    ## fib(1) and fib(2) can both be resolved to 1
    if n <= 2:
        return 1
    ## these numbers are summed until they reach fib(1) and fib(2)
    return fib_recursion(n-1) + fib_recursion(n-2)

Recursion and memoization:

Firstly, a definition of memoization that i copy pasted:

In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

this works in the same way as the recursive approach, except it adds to it with memoization;

this approach distinguishes between already calculated numbers and not calculated numbers in a dictionary (cache) so you never recalculate the same numbers.

However, this approach comes with a drawback in the form of taking up more memory.

## init for memo implementation
cache = {}
## implementation of fib function using recursion and memoization
def fib_memo(n):
    if n in cache:
        return cache[n]
    elif n <= 2:
        value = 1
    else:
        value = fib_memo(n-1) + fib_memo(n-2)

    cache[n] = value

    return value

Time complexity

(Note: i did not make these findings myself)

The complexity of the iterative Fibonacci series is considered to be liner O(n), but the problem comes when is N is large enough, so generally it will not be linear.

Recursive T(n) = O(1.6180)^n

Memoization T(n) = n

Important

in python recursion is less efficient to iteration however some other languages act differently

P.S repost because i accidentally put it on the share board before so i took that post down.

implementations of the fib function explained and analysed (memoization/recursion explained)