Optimize your recursive approach using memoization!
For beginners!
Published in
3 min readJun 9, 2021
What you will learn:
- How to implement memoization in a Fibonacci function.
What you need:
- Nothing!
Recommended:
- Knowledge of a programming language.
What is Fibonacci?
A Fibonacci sequence is a sequence where the next number is the sum of the two before it, the first two numbers are 1.
First 5 numbers of Fibonacci:1, 1, 2, 3, 5
Fibonacci with recursion
Every recursive function should have a base case, which makes sure that the function doesn’t call itself endlessly.
In this case, we’ll check if it’s 1 or 2, because we know that those two will have to be 1.
☝ The code stubs below will be written in Python.
def fib(n):
if n == 1 or n == 2:
return 1A fibonacci number is the sum of the two numbers behind it, so we can just call the function again, but with n — 1 and n — 2 instead.
def fib(n):
if n == 1 or n == 2:
return 1 return fib(n-1) + fib(n-2)
