Javascript – Introduction to recursion

0 / 1821
Javascript recursion

Today in this blog, I cover basic to advanced concepts of recursion in javascript. Recursion is a programming concept, which is not limited to javascript. It aims at solving complex problems by breaking them into smaller chunks and then collating the results altogether to return a final solution. This is achieved by creating a function which is delegated a complex task which is broken apart into smaller chunks and the same function calls itself until a base condition is met.

To explain more about recursion, we will take up some examples one by one starting with very simple basic fibbonacci series creator function followed by a function returning sum of N numbers

 

Fibbonacci recursion approach 1:-

JS Bin on jsbin.com

Visual explanation of the above approach:
fibonacci(10)
____|______________
|                            |
fib(8)               fib(9)
____|____        ____|_____
|            |       |              |
fib(6) fib(7)   fib(7) fib(8)

 

Fibbonacci recursion approach 2:-
Sum of N numbers recursively:-

 

The above code is a bit complex so I will break it down further to make it simpler and easier to understand. Below is the snippet of code taken from above jsbin.

// pass an additional param which will be used as function signature
console.log("Sum of N numbers where N=123", function (param, n) { 
    return param(param, n); // this will call the inner anonymous function
  }( 
    function (recurse, n) { 
      if (1 == n) // base condition
        return n; 
      else 
        return n + recurse(recurse, n - 1);		// recurse until n == 1
    }, 
    123	// input param 1+2+3+......+123
  ) );

Let’s try to understand bit by bit :-

function (param, n) {
return param(param, n);
}

The above line returns a function call which is referred to by the argument ‘param‘. Now let’s try to understand what is this param.

Let’s dig a bit deeper into the code. Combining the above code snippet with the arguments passed to the above anonymous function as below

function (param, n) {
return param(param, n);
}(
function (recurse, n) {
if (1 == n) // base condition
return n;
else
return n + recurse(recurse, n – 1); // recurse until n == 1
},
123 
)

I have colored the 2 arguments in red and green respectively to make it more clear as to what’s happening. The code snippet in red  which is an anonymous function, refers to the first argument i.e ‘param‘ and the number in green represents the second argument i.e ‘n‘. param represents a simple function which will be executed recursively until the base condition is met i.e until n reaches 1. The line return n + recurse (recurse, n-1), will keep on adding the different values of the parameter to the value returned by the recursive function call recurse(recurse, n-1) which equates to calling the anonymous function

function (param, n) {
       return param(param, n); 
}

Thus, in short we have indirectly renamed the outer function as recurse and calling it recursively from the inside anonymous function. Javascript interpreter checks the function signature based on which it maps recurse to the outside anonymous function  💡

 

 

Here is a simple javascript function to calculate factorial of a number recursively. It’s pretty self explanatory, so I need not explain it 🙂
JS Bin on jsbin.com

Comments

comments


An avid reader, responsible for generating creative content ideas for golibrary.co. His interests include algorithms and programming languages. Blogging is a hobby and passion.
loading...

Related Posts