Recursion: One thing you should understand before understanding Recursion
Part 1 :
When I planned to write a blog about recursion, I did a small research for the blogs already available about recursion. There are plenty of blogs that gives you a good knowledge about recursion. I have given the links of some of the best blogs I have read in the medium at last.
In this Blog we are going to cover about some common mistakes that naive programmers often forget while implementing the recursive function.
First, To some beginners I will give some simple definition about recursion
A process that calls itself.
You should have definitely heared the joke "To understand the recursion you should understand the recursion first", sounds recursive right?
But to me in javascript to understand recursion, we should understand the Call Stack .
if you understand this you will understand how the browser handles the function call and what happens behind the scene of a function call.
Call Stack
In almost all programming languges, there is a built in data structure that manages what happens when function are invoked. It is named the Call Stack
It follows stack data structure, which is nothing but last in, first out strategy. Any time a function is invoked it is placed (pushed) on the top of the call stack. When javascript sees the return keyword or when the function ends, the compiler will remove (pop)
I will give an example with a visual representation with the code below.
This program might seem silly but, it will be helpful to demonstrate the functions happening in call stack. At first when the wakeUp() function is called. the function gets added up in the call stack.
you could see the yellow highlighted marker, wakeUp() function has been added in the callStack. the wakeup calls two function takeShower(), eatBreakFast() and there is another function invoked inside the eatBreakfast() named cookFood(). All the invokes will get stacked up in the call stack.
Here is the clear picture of the total function called up. You see that takeShower() function is missing in the call stack, it is because the function has thrown a return and so It gets executed and popped out from the call stack.
So why should we care about the call stack ?
- You're used to functions being pushed on the call stack and popped off when they are done.
- When we write recursive functions, we keep pushing same function onto the call stack !
So there should be a stop to the function call before they go to infinite call and go into "stack overflow". Sound's new right I will explain about that in the next part of this blog.
As I promised in the beginning, here are one of the best blogs I read about Recursion
https://blog.angularindepth.com/learn-recursion-in-10-minutes-e3262ac08a1
Part 2
So, there are two things that you should remember whenever you are writing a recursive function.
- Base Case
- Different Input
Here is the basic idea of how the recursion works.
Invoke the same function with a different input until you reach your base case !
What does Base case mean here ? the condition where recursion ends. This is one of the most important concept to understand. And the Different Input refers that, each time when we call the function we send a different input to it.
Let me explain you with an example.
You can see that there are two conditions in the above snippet, The first one is Base condition which prevents the function call going to infinite and the next one is Different input which supplies one count reduced as parameter to the function each time.
So most people Go wrong with these things, They either do not declare a base condition or different input condition. So the recursive function goes as infinite and throws the error, the call stack size exceeded. This term is generally called as "Stack Overflow", yes the call stack is overflowing.