Recursion is one of the important and challenging topics for many developers to understand and master. Recursion is also a foundation for many other algorithms and techniques. Developers often get confused and it gets difficult to visualize what is happening at each stage during recursion execution.
Here is an article explaining the working of Recursion with the help of a diagram and many examples.
What is Recursion?
A Recursion in more formal terms is a computer programming technique that involves a certain process in which a function calls itself again and again until the given condition is met. It is generally used to solve problems where its solution itself depends on a smaller instance of it.
The basic idea is to divide the bigger problem into a number of smaller problems, solve them and then combine them to solve that bigger problem.
Note:- In order to get better in recursion, I would suggest you should have a thorough knowledge of Stack Data Structure and its LIFO principle.
Also read, Simple Explanation of Stack and Queue with JavaScript
Example
Print 5 numbers using the Recursion method:-
function recur(n){
if(n == 6){ // base class
return
}
console.log('Current value --', n)
recur(n+1)
}
recur(1)If you look at the code you would notice a few things, initially, when we invoke recur function, the current value of n is 1. First, the compiler checks the base function, as the value of n is not 6 we first print the value and then invoke the same function but increase the n value by 1.
Again the compliers check the base function, as the value is not 6, it prints the value and then again calls the same function with and sends an increased new n value. At last, when the n value becomes 6, the function returns and we successfully printed 5 numbers with the help of recursion.
Why Recursion is important?
Recursion is an important concept in the computer science branch. Many algorithms like Depth First Search, Merge sort or Quick sort is based on Recursion. Here are a few advantages of using Recursions.
- Recursion helps in solving bigger complex problems in a simple way.
- You can also convert any recursive solution into iteration and vice versa.
- It helps in breaking bigger problems into smaller problems.
Also read, Understanding Array, String, and Object Data Structure with JavaScript
Understanding Recursion using Diagram
In order to understand how recursion works behind the scenes, explaining each step of recursion’s execution with the help of diagrams is the best way of understanding. So before we move on, let us take one small real-life example! Print a 5! factorial with the help of recursion.
Here is the code of 5! factorial using recursion:-
function fact(n){
if(n <= 1){
return 1
}
return n * fact(n - 1)
}
let res = fact(5)
console.log(res) // 120Now let us understand each step with the help of a diagram:-
Step 1, n value is 5
Initially, when the recursion is function is called for the first time, let say it is the main function, so when the main function is called its execution context gets pushed inside the call stack. When the main function is called, it will check the base condition which is false right now, then it is calling itself but with value n-1, which is 4.
Note:- One important point to understand about the call stack is till the function is not finished executing, that function will remain in the call stack, and once the function is finished executing it gets removed from the call stack.
Base Condition
A base condition is said to be a condition where the recursion will stop making new calls. It is used to avoid the compiler stack getting over-flow and recursion to call itself infinitely. For example, in this example, we give a base condition where if the value of n becomes equal to 0 we would return 1, and then the program will stop calling itself.
Note:- Every time a recursion function call itself, each function takes a memory space even though the function remains the same. Thus if we don’t have any base condition, a time will come when no memory space is left, thus compiler will. throw stack overflow error.
Step 2, n value is 4
A fresh new function is passed on to the top of the main function in the call stack. Again the compiler checks the base function, the base condition is not true as the current value of n is 4, then again goes down and calls itself but with will value 3.
Step 3, n value is 3
Again, a new fresh new function is passed on to the top of the last function in the call stack. the compiler checks the base function, the base condition is not true as the current value of n is 3, then again goes down and calls itself but with will value 2.
Step 4, n value is 2
Again, a new fresh new function is passed on to the top of the last function in the call stack. the compiler checks the base function, the base condition is not true as the current value of n is 3, then again goes down and calls itself but with will value 1.
Step 5, n value is 1
Again, a new, fresh function is passed on to the top of the last function in the call stack. the compiler checks the base function, but this time base condition is satisfied and instead of calling itself it simply returns with value 1.
Step 6, the return value is 1
And then the top function after executing gets removed from the stack and the flow of the program comes back to the last function with a return value of 1.
Step 7, the return value is 2
Current functions returns n * fact(n – 1), in which current value of n is 2 and return value from last function ( fact(1)) is 1, so after this function also get removed from stack with return value 2.
Step 8, the return value is 6
Now the current function returns n * fact(n – 1), in which the current value of n is 3 and returns a value from the last function (fact(2)) is 3, so after this function also gets removed from the stack with the return value 6.
Step 9, the return value is 24
Current functions returns n * fact(n – 1), in which current value of n is 4 and return value from last function (fact(3)) is 6, so after this function also get removed from stack with return value 24.
Step 10, the return value is 120
Finally coming to the main functions, it returns n * fact(n – 1), in which the current value of n is 5 and returns a value from the last function (fact(4)) is 24, so after this function also get removed from the stack with return value 120.
Also read, Simple Explanation of Tree traversal Operations with JavaScript
Types of recursion
There are also different types of recursion:-
Direct Recursion
In Direct Recursion, a recursive function calls itself within the same function.
function sumNatural(n){
if(n == 1){
return 1
}
return n + sumNatural(n-1)
}
let res = sumNatural(5)
console.log(res) // 15Indirect Recursion
In Indirect Recursion, two or more recursive functions call each other in a circular manner.
function odd(n){
if(n > 10){
return
}
console.log('this is odd number ---',n)
even(n+1)
}
function even(n){
if(n > 10){
return
}
console.log('this is even number ---',n)
odd(n+1)
}
odd(1)Tail Recursion
In Tail Recursion, the function recursively calls itself at the end of the function, after which no statement or function exists.
function calc(n){
if(n == 0){
return
}
console.log(n)
calc(n-1)
}
calc(5) // 5 4 3 2 1Head Recursion
In Head Recursion, the function recursively calls itself at the starting of the function, after which there exist few statements or functions.
function calc(n){
if(n == 0){
return
}
calc(n-1)
console.log(n)
}
calc(5) // 1 2 3 4 5Linear Recursion
In Linear Recursion, the recursive function calls itself once each time only and grows linearly in proportion to the given input size and base condition.
function natSum(n){
if(n <= 1){
return 1
}
return n + natSum(n - 1)
}
let res = natSum(5)
console.log('Sum of first 5 natural number is',res) //15Tree Recursion
In Tree Recursion, the recursive function calls itself more than one time and grows non-linearly in proportion to the given input size and base condition.
function fibbo(n){
if(n <= 1){
return n
}
return fibbo(n - 1) + fibbo(n - 2)
}
for(let i = 0; i <= 10; i++){
console.log(fibbo(i)) // 0 1 1 2 3 5 8 13 21 34 55
}Also read, Understanding Binary Search Trees with Js
How to solve a Recursion Program
-
Identify if you can break down problems into smaller problems.
- Write the recursion relations if needed.
- Draw the recursion tree.
- About the tree:-
- See the flow of functions, and how they are getting into the stack.
- Identify and focus on left tree calls and right tree calls.
- Draw the tree and pointers again n again using pen and paper, and use a debugger to see the flow.
- See how the values and what types of values are returned at each step.
- See when the function calls will come out of the stack.
Also read, Introduction to Tree Data Structure
Final Words
Let us face it, Mastering Recursion is hard! When we were kids we weren’t taught how to think and visualize in a recursive way. You need to practice and practice more and more questions, and analyze logs at each stage to learn the recursive patterns. Try to solve any program which you think can be solved using recursion, and practice it.
If you like this article do share more with your friends and colleagues and also check out more articles on various topics like Data Structure algorithms with JavaScript, React, Java, Javascript, and other tutorial articles.