Learn to Code via Tutorials on Repl.it!

← Back to all posts
implementations of the fib function explained and analysed (memoization/recursion explained)
h
rafrafraf (1389)

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.

check this post to see my implementation of the recursive fib func with memoization in one line :)

Comments
hotnewtop
DanielCoore (2)

I noticed that for your iterative version you were storing intermediate results; but that takes time to manipulate the list. Since we need only the last two values, we can do away with the list altogether. I implemented another version called fib_const_space that is also iterative and goes a little faster than your original iterative version.

rafrafraf (1389)

@DanielCoore thats awesome! honestly the iterative one was just one I tried to make as quickly as possible without much thought to if i could improve it as i was mostly focused on the others.. comment the link to your repl though id love to check it out!

DanielCoore (2)

@rafrafraf Here it is: https://repl.it/@DanielCoore/implementations-of-fib

Sorry, I'm new to Repl.it and I was just poking around. When I forked your code, I thought that there might have been a way for you to see it (I thought it was automatically shared with the original owner).

rafrafraf (1389)

@DanielCoore just checked it out and it looks good nice man!

DanielCoore (2)

@rafrafraf Cool! Feel free to use it to update your tutorial here if you wish.

CodingRedpanda (179)

@rafrafraf
this is nice, i have never worked with Fibonaci (i know i spelled that wrong) in a language, so this helped!

JBloves27 (1715)

Nice job! This really helped me understand it more! :D

Wumi4 (481)

Very helpful! I never made a working fibonacci series before lmao.

rafrafraf (1389)

@Wumi4 thanks! i hope this will help you make your own implementation :)