Javascript – Introduction to recursion

0 / 2687
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.
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.

Related Posts