Every Beginner is afraid of Recursion until one gets the knack of it. I hope after reading this series, Recursion will sound more helpful than confusing.
What is Recursive function?
A recursive function is defined as a function that calls itself to solve a smaller version of its task until a final call is made which does not require a call to itself Technical much? 😅
THE INTUITION
Let's see a Real-world example to understand.
Suppose you are sitting in the leftmost seat in the top row in Cinema hall 😛 and Someone Asks you how many rows are there?
Now there can be two approaches to solve this:
Approach-1) You stand up and count every row and tell the answer.
Approach-2) Recursive Approach: Or You can ask this same question from the person who is sitting in the next row to you (Subproblem) and add 1 to his answer (to include your row in the count). (You won't need to stand-up and count 😆)
Now When we asked the same question to the person in the next row, He does the same (ask the person in the next row to him and adds 1 to his answer and tells us the final answer). And Every person in every row does the same!
Except for the person in the last row, He has no row in front of him, So he reports 1 as an answer. (Base Case)
The second-row person gets 1 as the answer, adds +1 to include his row, and reports to the third-row. And similarly, Every person in the upper rows, get an answer, adds 1 to the answer to include themselves and report their final answer to the upper row (who asked them the question)
Similarly, you get the answer, You add +1 to the answer and report the final answer to someone who asked you.
So The approach we used is called the Recursive Approach because it involved solving subproblems (similar and smaller) and doing extra work (adding +1). It also involved the Base case (simplest possible case) which is the final call and does not require further calls.
When to use Recursion?
When Solution to a problem can be built upon solution of similar and smaller subproblem, Then we can use Recursion.
Let's write a function to get the factorial(n) Ex: We want the factorial(9), We can get the solution by multiplying 9 to factorial(8).
factorial(n) = n * factorial(n-1)
and the smallest possible valid input to factorial function can be 1. And we know, factorial(1) = 1. So this will be our base case. The code will be:
int factorial(n){
if (n==1)
return 1;
int ans = n * factorial(n-1);
return ans;
}
Many blogs in the series are on the way. Stay Tuned 🎈