Recursion in Js ….
Hi Guys in this Blog we will discuss about Recursion in JavaScript. So let’s get started .
What is Recursion?
So in layman language we can say recursion is A process (a function in our case) that calls itself.
Why do we need to know this ?
The easy and simple answer to this question is it’s everywhere , If we take up any Javascript built in function like JSON.parse / JSON.stringify , we will see these functions are internally written in Java using recursion concept. Recursion is also used internally in document.getElementById , and it’s very much useful on DOM traversal algorithm . Recursion concept is also useful for Object traversal , it’s very common in more complex algorithm , and it can be used as a cleaner alternative of iteration.
Now let’s see How recursive functions work ?
Now before going to the concept of how recursive function works let’s see how a function works first .
In almost all program language there is a built-in data structure that manages what happen when function are invoked , it is called the Call Stack , It’s s a stack data structure .
Anytime a function is invoked, it is placed (push) on the top of the call stack.
When JavaScript sees the return keyword or when the function ends, the compiler will remove (pop) the function from the top of the call stack.
Let see following code:
function takeShower(){
return "Showering!"
}
function eatBreakfast(){
let meal = cookFood()
return `Eating ${meal}`
}
function cookFood(){
let items = ["Oatmeal", "Eggs", "Protein Shake"]
return items[Math.floor(Math.random()*items.length)];
}
function wakeUp() {
takeShower()
eatBreakfast()
console.log("Ok ready to go to work!")
}
wakeUp()So we are having a chain of function calls here, first we are calling wakeUp() function, which are having two functions into it takeShower() and eatBreakfast() , then we are having console.log to indicate the end of the whole function chain. takeShower() function is just returning a string value, whereas eatBreakfast() function is having another function called cookFood() function and it returning the value which is getting returned from cookFood() . In cookFood() function we are having one array which is having the array of food names what can be cooked , we are picking any food randomly from the array and returning it to eatBreakfast() function, So to understand the flow of the execution of these function chain let see the chrome dev tool :
To check the flow in the dev tool we can open our Javascript code in live server , and open the host link in google chrome , then right click on the browser window you will see a option inspect, then the dev tool will get opened , initially the Elements tab will be open , click to source tab where you will see your js file present in the source code , once you click on that you will see your js code , then we have to add debugger to the code , for that we first we have to consider what are breakpoints we will be adding on our code , since we will be checking the flow of the function chain we will set our breakpoints on the point where wakeUp() function is called . To set the debugger we just have to click on the line number where we want to add it , like in our case , line number 25 where wakeUp() function is called. By debugging a piece of code we can check each and every stage of a function execution. So in right side dev tool you will see there is a dropdown called Call Stack , now let’s follow that tab while we execute the our function , if we reload the page we will see anonymous function is getting added in call stack first , these anonymous function is the main execution thread of the page. If you notice in the right hand top in dev tool we are having a button like right pointing arrow with a dot in front , if we click on the it will show us the line by line execution of the function, so let see how the flow works. After anonymous function , wakeUp() function will be pushed at the top of the call stack , then since wakeUp() is calling takeShower() function, takeShower() function will be pushed to the top of the stack , in takeShower() function since browser have encountered a return statement it means the takeShower() function execution is completed, takeShower() function will be popped out from the call stack , again the control will go back to wakeUp() function, now eatBreakfast() function will be pushed in the call stack , eatBreakfast() is having a function cookFood(), so cookFood() will get pushed into the call stack , cookFood() function will take a random food item from items array and will return it to eatBreakfast() function , since browser encounters return statement on cookFood() function it will pop out cookFood() from call stack, then the control will go on eatFood() and since it encounters a return statement , it will pop out eatFood() function from the call stack and finally the call stack will go to wakeUp() function and will encounter end of function with console.log so browser will pop out wakeUp() function from call stack , and call stack will be empty , So this is how call stack works on executing a javascript code.
So in normal function , we have seen the function is being pushed on the call stack and popped off when they are done , for recursion function we will keep pushing same function on the call stack with different parameters.
So let’s see the execution flow of a recursive function:
function collectOddValues(arr){
let newArr = [];
if(arr.length === 0) {
return newArr;
}
if(arr[0] % 2 !== 0){
newArr.push(arr[0]);
}
newArr = newArr.concat(collectOddValues(arr.slice(1)));
return newArr;
}
collectOddValues([1,2,3,4,5])Here we are collecting the odd values from the array using recursion. So we are having collectOddValues function where we have created an arr newArr , then we are checking whether the first element of arr is even or odd , if it’s odd we are pushing the element in newArr , then we are recursively calling the collectOddValues function and updating it in newArr. All the recursion function should have a base condition , where the function should stop and return some values , for this we are checking if arr is having 0 element we will return the value of newArr . Now let’s see the execution of the function in dev tool, So first function that will be pushed to the call stack is collectOddValues([1,2,3,4,5]) , on that function we are checking whether the parameter arr is having any element or not if it’s not having any element it will return newArr , else it will check if the first element is odd , if it’s odd the element will be pushed to newArr arr , then we will concatenate returned value of collectOddValues([2,3,4,5]) so collectOddValues([2,3,4,5]) will be pushed in callstack , then similarly collectOddValues([3,4,5]) , collectOddValues([4,5]), collectOddValues([5]) and collectOddValues([]) will be pushed on the callstack . So when collectOddValues([]) will be called , it will check the whether there is any element in the arr , since arr is empty it will meet base case and will return newArr which is [], then control will return to collectOddValues([5]) ,where newArr will become [5] so it will return [5], then control will return to collectOddValues([4,5]) ,where newArr will remain [5] so it will return [5], then control will return to collectOddValues[3,4,5]), newArr will become [3,5] so it will return [3,5] , then control will return to collectOddValues([2,3,4,5]) , newArr will remain [3,5] so it will return [3,5] , finally control will return to collectOddValues([1,2,3,4,5]) where newArr will be become [1,3,5] and finally it will return the array [1,3,5]
Now let’s explore few key features we should always consider while writing a recursion function:
A> Adding Base Cases : While defining recursion function we should define a base case that will lead to the end of the recursion call , otherwise recursion call will happen in infinite loop. Which will lead to Maximum call stack size exceeded error , because the recursion function will start executing in a infinite loop , and will get pushed in call stack infinite times which will exceed the maximum size of the call stack. Please check the below execution of the code where we have not kept any base case.
B> Adding return statement or you can say adding correct return statement: While defining recursion function we should always have a return statement , otherwise none of the recursion function will stop executing . Which will again lead to maximum call stack size exceeded error ,Please check the below execution of the code where we have replaced the return statement with console.log .
C> Adding different parameter to recursion function in each iterative call: While declaring recursive function we should always call function with different parameter in each iterative call, otherwise always recursive function will be pushed into call stack with same parameter, which will never meet the base condition means none of the function will get returned, which will again lead to maximum call stack size exceeded error, or Stack overflow error , Please check the below execution of the code where we are always passing same parameter while calling recursion function .
Next topic we will be discussing is:
Helper Method Recursion
So far all the recursion function we have written are single stand alone functions , we have called factorial outside the function , and factorial itself calls factorial .
function factorial(num){
if(num === 1) return 1;
return num * factorial(num);
}
factorial(4)With Helper Method Recursion we will have outer method here, then inside that we have our recursion function, and this recursive function calls itself.
function outer(input){
var outerScopedVariable = []
function helper(helperInput){
// modify the outerScopedVariable
helper(helperInput--)
}
helper(input)
return outerScopedVariable;
}So why we need this helper method recursion , let’s say we are declaring variable result = [ ] which we will be using to store all odd elements from a given array . If we are doing it through recursive way, no matter what we put after this everytime the result will get reset to [ ] array. So How we are going to collect the data , the most easy solution is to put the result array outside the function , so rather than putting the result array nowhere globally we will be using helper method function , what will wrap the recursion function.
function collectOddValues(arr){
let result = []
function helper(helperInput){
if(helperInput.length === 0) {
return;
}
if(helperInput[0] % 2 !== 0){
result.push(helperInput[0])
}
helper(helperInput.slice(1))
}
helper(arr)
return result;
}
collectOddValues([1,2,3,4,5])Now let’s see Pure Recursion Approach :
Let’s see the pure recursion approach of the same piece of code:
function collectOddValues(arr){
let newArr = [];
if(arr.length === 0) {
return newArr;
}
if(arr[0] % 2 !== 0){
newArr.push(arr[0]);
}
newArr = newArr.concat(collectOddValues(arr.slice(1)));
return newArr;
}So this piece of code is the pure recursion version , where we replacing the helper method recursion logic with pure recursive logic , Here are few tips for writing pure recursion :
For arrays, use methods like slice, the spread operator, and concat that make copies of arrays so you do not mutate them.
We have to keep in mind that strings are immutable so you will need to use methods like slice, substr, or substring to make copies of strings.
To make copies of objects we can use Object.assign, or the spread operator.
Now what about calculating Big O in case recursion ?
Measuring time complexity is relatively simple. You can measure the time complexity of a recursive function as then number of recursive calls you need to make relative to the input.
Measuring space complexity is a bit more challenging. You can measure the space complexity of a recursive function as the maximum number of functions on the call stack at a given time, since the call stack requires memory.
Tail Call Optimisation:
Tail Call Optimisation is a concept where we can optimise a recursive function. Compilers usually execute recursive procedures by using a stack. This stack consists of all the pertinent information, including the parameter values, for each recursive call. When a procedure is called, its information is pushed onto a stack, and when the function terminates the information is popped out of the stack. Thus for the non-tail-recursive functions, the stack depth (maximum amount of stack space used at any time during compilation) is more. The idea used by compilers to optimize tail-recursive functions is simple, since the recursive call is the last statement, there is nothing left to do in the current function, so saving the current function’s stack frame is of no use. So ES2015 allows for tail call optimisation, where you can make some function calls without growing the call stack. By using the return keyword in a specific fashion we can extract output from a function without keeping it on the call stack. Unfortunately this has not been implemented across multiple browsers so it is not reasonable to implement in production code.
Conclusion:
So let’s recap what we have learned in this blog :
- A recursive function is a function that invokes itself
- Your recursive functions should always have a base case and be invoked with different input each time
- When using recursion, it’s often essential to return values from one function to another to extract data from each function call
- Helper method recursion is an alternative that allows us to use an external scope in our recursive functions
- Pure recursion eliminates the need for helper method recursion, but can be trickier to understand at first.
So we have covered almost all the topics which are related to recursive concept, Hope this will be helpful for you !! Please check out my Github repo for the reference of the codes discussed in this blog :
HAPPY CODING :)
