Solving an algorithm using recursion.

3 min readFeb 6, 2021

A recursive function is one that calls itself to solve itself. A clear demonstration of this process is creating a function to solve a Fibonacci sequence. A Fibonacci sequence is when each number is the sum of the two preceding ones, starting from 0 and 1. So Fibonacci of 1 is 1, Fibonacci of 2 is 1, and Fibonacci of 3 is 2 because F(n) = F(n — 1) + F(n — 2), for n > 1.

So when writing a function to solve for such it is important to keep in mind that Fibonacci of 3 (or in notation f(3)) is equal to f(2) + f(1). When going through a series of computations it would come in handy to have a storage of previous results. Say hello to memoization. Memoization is essentially the practice of having a place where we store results of computations we’ve already done, in order to refer back to them in order to speed up our program. So in this case instead of going through and computing every number in a Fibonacci sequence we can just refer to the previous two that we’ve memoized and add them together.

In practice it might look something like this

var fib = function(n) {
    
    let memo = {}
};

First we start with our basic function where n represents the number we’re trying to put through the Fibonacci sequence and then we set up an empty object for our memoization.

var fib = function(n) {
    
    let memo = {}    const computation = (number) =>{
         if(memo[number]) return memo[number] 
         if(number == 0) return 0    
         if(number == 1) return 1 
       
    
    }
};

Next, we want to set up our recursive function with the basic parameters. I’ve named it computation and it accepts an argument of number, which is going to be the “n” that is passed into the var fib function.

From there, it is important to establish basic edge cases so that the function can run properly. First, if the number that is being passed into our computation function already exists within our memo object, simply return that value so we don’t bother recomputing the math when we don’t have to. Then our next step is to establish the start of our memo if the number passed in is 0 or 1 because these are the only two numbers that will not be able to fulfill the basic logic of the Fibonacci sequence.

var fib = function(n) {
    
    let memo = {}
    
    const computation = (number) =>{
        if(memo[number]) return memo[number] 
        if(number == 0) return 0    
        if(number == 1) return 1 
        memo[number] = computation(number-1) + computation(number-2)
            return memo[number]
    
    }
   return computation(n)
};

Finally, we apply the recursive part of the function. What we’re saying is “if the number is not present in the current memo and that number is also not 1 or 0, create a new key value pair within the memo object where the key is the argument of number and the value is equal to the the number that results from the Fibonacci sequence from that number.” We fulfill the Fibonacci sequence by applying that same function and logic to the numbers that are that number — 1 and that number — 2 and then adding them together. Lastly, we make sure we return the value from that computation in our recursive function as well as returning the value of the computation function itself to the fib function.

Solving an algorithm using recursion.

Written by Tim Rinkerman