Definition: A process or a function that calls itself.
Where is it used ???
(Other than our own code)
- JSON.parse / JSON.stringify inside JavaScript engine is often written recursively.
- document.getElementById and DOM traversal algorith are often written recursively.
- Recursion is also seen with more complex data structures.(Trees and Graphs)
- At times it is seen as a cleaner alternative to iteration.
Any time a function is invoked, it is placed on the top of call stack. When JavaScript sees the return keyword or whenever the function ends, compiler will remove it from stack. We are used to functions being pushed on the call stack and popped off when they are done. When we write recursive functions we keep pushing new functions onto call stack.
How recursive functions work?
We invoke the same function with a different input until we reach the base case.
Base Case:It is the condition for which solution is provided. The solution for the bigger problem is expressed in terms of smaller problems.
function factorial(num){
if(num===0||num===1) //Base Case
{
return 1;
}
else return num*factorial(num-1);
}
Common recursion pitfalls
- Errors in the base case
function factorial(num){
if(num===1||num===1) //Base Case
{
return 1;
}
else return num*factorial(num-1);
}
- Forgetting to return or returning wrong thing
function factorial(num){
if(num===0||num===1) //Base Case
{
return num ;
}
else return num*factorial(num-1);
}
- Instead of return using console.log for base case.
function factorial(num){
if(num===0||num===1) //Base Case
{
console.log(1);
}
else return num*factorial(num-1);
}
- Maximum call size stack exceeded / stack overflow.
function callMyself(){
callMyself();
}
callMyself();
Top comments (0)