Note: use the github provided TOC for navigaing.
There is two parts of recursive solution,
===============================================================================
|Easiest way to Approach Recursion problems |
|"Magical" Recirsion Rule = "Principal of Methematical Induction(PMI)" |
===============================================================================
| 1. Figure out the base case. There can be multiple base cases |
| 2. Assume Sub Problems can be solved bu recursion (sutomatically)(IMP) |
| 3. Using the sub-problem write the answer for the current problems. |
===============================================================================
Say you need to find factorial of 3(3!). you can solve it via recursion but you can also solve it using recursion too.
Factorial(0) =1
as 0!=1
.Factorial(N-1)
can be computed using recursion, we need to assume this.Factorial(N) = N * Factorial(N-1)
.int Factorial(int n){
//base case
if(n==0){
return 1;
}
// recursive case
int small_ans = Factorial(N-1);
int factorial = n * small_ans;
// return the calculated value
return factorial;
}
int main(){
int n;
n = 3;
cout<<Factorial(3);
}
As you can see in the picture, there are two calls happens, one is top down call
and another is bottom up call
.
top down call
when execution of the recursive case happens, the function call from the recursive case keeps on happening untill it hits the base case
.bottom up call
, after hitting the base case it returns the base value and the smaller problems get solved one by one untill the first call gets its value.
Function calls happens via call stack, the rectengle represents the call stack. and in thaat call stack we have main func and all the variables associated with the func are in stack memory, bcoz of that N is all the stacks, when Factorial()
gets called a stack memory gets assigned to the Factorial()
where N=5, then internally the afain Factorial()
call happens(in the small_ans line) and it gets a stack memory too, but N is now 5-1=4;but value of Factorial(4)
is unknown, so again function call happens, and this goes on untill it hit the base case, when it hit the base case it returns some value, and the stack memory gets deleted(the top memory), and this returned value gets passed to smaller problem (below stack function calls where N=1) and small_ans
gets calculated and that stack memory gets deleted, and this keep going on untill it comes to main, and from main the value is printed.
https://dynalist.io/d/LoGwqWPmqCT3IoPxJqV2SlZp