Impress Interviewers with Recursion

What is Recursion ?

Recursion is a process in which a function calls itself as a subroutine. … Functions that incorporate recursion are called recursive functions. Recursion is often seen as an efficient method of programming since it requires the least amount of code to perform the necessary functions.

Two of the most common questions you’d be asked in an interview for Recursion problems would be Fibonacci and Matrix.

Today I’ll speak about the best Recursion Algorithm for Fibonacci.

First the basic way:

function Fib(n){
     if(n <= 1) return 1;
     
     return fib(n - 1) + fib(n - 2)
}

Let me explain :)

Basically, any fib(1) will be 1, but the process to break down the number from 5 for example, will be fib(4) + fib(3), and we will break down 4 till it gets to 1. consider how many ones will be added to each.

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

If you still having a hard time to understand it try this:

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

And keep breaking down all fibs till you reach one, automatically the condition to break down the recursion once n ≤ 1

If this makes sense to you, and you can solve it, you’ll have another question,

HOW CAN WE IMPROVE THIS RECURSION SOLUTIONS ??

Yes, if you think about it, our fib function will do the same process many times if n is a big number like 20. you’ll break down each number and repeat the fib function on it.

Example:

fib(5) = fib(4) + fib(3)

you will still break fib(4) to fib(3) + fib(2) which you broke on fib(3).

Improved Recursion:

Imagine we store in an object all the value for fibs so we don’t have to repeat the function many times, this will save so much time.

function SlowFib(n){
     if(n <= 1) return 1;
     
     return fib(n - 1) + fib(n - 2)
}
function improvedFib(fn){
   cashe = {}
return function(...args){
        if(cashe[args]){
           return cashe[args]
        }
        const result = fn.apply(this, args);
        cashe[args] = result;
  };
}
fib = improvedFib(slowFib)

• We will rename our fib function to slowFib function and use it into our improvedFib.
• Improved Function will store every fib of number into our Cashe object
• Every time we hit a number we don’t have in the Cashe object we run the slowFib on it and store in to our Object.
• (…args) is when an ES6 operator when you’re not sure how many arguments this function will take, and make them an array.

For more resources about Recursion check my Blog:

Recursion in Ruby ‘CLI Project’