How Recursion Works in Javascript
Real-Life Examples with code
“ In order to understand recursion, one must first understand recursion. ” And once you understand recursion you are done…😃😃
Recursion comes directly from Mathematics, where there are many examples of expressions written in terms of themselves. For example, the Fibonacci sequence is defined as:
F(i) = F(i-1) + F(i-2).
Or the Factorial sequence is defined as:
n! = n * (n — 1) * (n — 2) * (n — 3) ….
✨ What is recursion in programming?
In programming terms, recursion is a function calling itself until a “base condition” is the correct output.
In other words: to solve a problem, we solve a problem that is a smaller instance of the same problem, and then we use the solution to that smaller instance to solve the original problem.
👩🏻🦰 : oh, I got it. But, What is a recursive function?😕
🔸 A function that calls itself is called a recursive function. and this technique is known as recursion.
For a recursive algorithm to work, the smaller sub-problems must eventually arrive at the base case. In simple words, any recursive algorithm has two parts:
Part 1: Base Case: a terminating condition where a function can immediately return the result. This is the smallest version of the problem for which we already know the solution.
Part 2: Recursive Structure: Designing a solution to a problem via the solution of its smaller sub-problems i.e same problem but for a smaller input size. We continue calling the same problem for smaller input sizes until we reach the recursion’s base condition.
🧿Theory is boring, right? we want a real-life example…
For example, we can define the operation as:
“find the way to your girlfriend’s home”😜
🔸 If you are already at your GF’s home, stop moving.
🔸 If not, try to find her home and Take one step toward home.
Here the solution to finding your way home is two steps (three steps actually). First, we don’t go home if we are already home.
Secondly, we do a very simple step that makes our situation simpler to solve. Finally, we redo the entire algorithm.
How would you write a recursive “algorithm” for finding a shopping mall?
Function “Find shopping mall”:
step 1: Ask Someone which way to go. (they point “that away”)
step 2: Move “that away” until unsure
step 3: Find shopping mall. (redo the entire algorithm)
✨ Another Recursion Example in Real Life:
Suppose you are standing in a long queue of people. How many people are directly behind you in the line?
Condition:
🔸 one person can see only the person standing directly in front and behind. So, one can’t just look back and count.
🔸Each person is allowed to ask questions from the person standing in front or behind.
How can we solve this problem recursively?
Solution:
🔸 you look behind and see if there is a person there. if not, then you can return the answer “0”. if there is a person, repeat this step, and wait for a response from the person standing behind.
🔸 Once a person receives a response, they add 1 for the person behind them and respond to the person that asked them or the person standing in front of them.
Now it’s time to take a simple & popular problem and solve it with recursion…
✨ Let’s try to Understand Recursion Via Finding n” th Factorial:
factorial, in mathematics, the product of all positive integers less than or equal to a given positive integer and denoted by that integer and an exclamation point.
factorial Ten is written 10! meaning 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 × 10.
factorial Nine is written 9! meaning 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9.
factorial Eight is written 8! meaning 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8.
factorial Seven is written 7! meaning 1 × 2 × 3 × 4 × 5 × 6 × 7.
factorial Six is written 6! meaning 1 × 2 × 3 × 4 × 5 × 6.
factorial Five is written 5! meaning 1 × 2 × 3 × 4 × 5.
look at the above example:
5! = 1 × 2 × 3 × 4 × 5.
6! = 1 × 2 × 3 × 4 × 5 × 6.
or we can say that:
6! = 6× factorial of 5
or
6! = 6 × 5!
Again:
6! = 1 × 2 × 3 × 4 × 5 × 6.
7! = 1 × 2 × 3 × 4 × 5 × 6 × 7.
or we can say that:
7! = 7 × factorial of 6
or
7! = 7 × 6!
Now, what is the factorial of n?
we can write: n! = n × (n-1)th factorial
or, n! = n × (n-1)!
If we calculate the value of the (n-1)th factorial, we can easily calculate the value of the n”th factorial.
It means we can solve the problem of input size n with its smaller problem of the input size (n-1).
In other words, we can solve this problem by using the idea of recursion!
Suppose we have a function named “factorial”, the function factorial(n) and factorial(n-1) return the value of the n”th and (n-1)th factorial,
then we can write the following recursive structure:
factorial(n) = n × factorial(n-1)
🔥Now let’s dive into code:🔥
Here is a recursive function to calculate n’th factorial
function factorial(n){
//base case
if(n == 0 || n == 1){
return 1;
//recursive case
}
else{
return n * factorial(n-1);
}
};We can solve the same problem by using a regular for loop:
function factorial(n){
let answer = 1;
if (n == 0 || n == 1){
return answer;
};
else{
for(var i = n; i >= 1; i--){
answer = answer * i;
};
return answer;
};
};Pro: Takes less memory than the recursive implementation.
Con: The code is lengthier than that of the recursive implementation.
🧿 Here is another recursive function to calculate n’ th Fibonacci:
the sequence is defined as:
F(i) = F(i-1) + F(i-2).
function fibonacci(num) {
if(num < 2) {
return num;
}
else {
return fibonacci(num-1) + fibonacci(num - 2);
}
}✨How Does Recursion Works in the Background?
If we draw the flow of recursion for the above factorial program, one can find this pattern: we are calling factorial(0) last, but it is returning the value first. Similarly, we are calling factorial(n) first, but it is returning the value last.
Did you find some Last In First Out (LIFO) smell for recursive calls and return values?
Yeah, you got it! Behind the scene, the compiler uses a stack data structure to simulate recursion and deliver the correct output. We call this stack:
Call Stack!
🔸 Order of recursive calls: larger problem to smaller problem
factorial(n) -> factorial(n — 1) -> … -> factorial(i) -> … -> factorial(1) -> factorial(0)
🔸 Order of return values: smaller problem to larger problem
factorial(0) -> factorial(1) -> …-> factorial(i) -> … -> factorial(n — 1) -> factorial(n)
Later, I will write a separate article about call-stack. call stack deserves it.
Well, that’s it for today. I hope this tutorial helps you to understand recursion. If you have any questions or confusion about this tutorial please don’t hesitate to let me know…
happy Programming.💕
