Recursion
Finally i got what i was seraching for...The total insight on Recursion...
How it flows in a program...how it stacks ad unstacks and operates.
Let us begin.
Let us perform a recursive programming for finding the multiplication of two numbers.
NOTE: i chose this task as it is a bit ahead in class of the factorial recursion and behind the fibonacci series generation....
THEORY
Basic of multiplication is that we want to add a relatively larger series of same number.
i.e. 2+2+2+2+2+2+2+2 +2+2
Gosh it was boring and hectic to type it…see !
So we multiply.
No. of 2s multiplied by 2 i.e. 10X2=20
Note: I took 10X2 and not 2X10 because it fits in to my recursive program which is coming ahead. Theres absolutely no problem and the program needs just a minor change if you wanna do it the other way round. For now lets go on with what I say…
The Recursive Multiplication
To perform the above multiplication operation we use recursion.
As in factorial we shred the number by factor of 1 in each run of the function similary we will have two numbers to multiply , let us suppose3 and 2.
3 will be shreded in each step and will be added to 2 like in
3 X 2
= 2 X 2 +2
=1 X 2 + 2 + 2
=0 X 2 +2 + 2 + 2
=2+2+2
=6
Now we need to convert this mathematical idea into an expression which on running each step shall give us the corresponding mathematical steps
Try thinking a bit for a function…
The line 3x2=2x2+2 can best help one…It helped me !
The equivalent expression of above is
Mul= (a-1)*b+b;
But its not the expression which can be put into our recurvie function.
We wil advance and reach to the concept…trust me !
THE CONCEPTwith the multiplication question
Now let us look at the core concept of recursion and the insight of the operation.
Look at the following code as it does the multiplication operation …and I’l tell u why and how !
int recur(int a,int b)
{
if(a==0)
return 0;
else
{mul=recur(a-1,b)+b; // let this line be refered as Line A.
return mul;
}
}
The line A is the master line which does our multiplication operation.
The downward move
mul=recur(a-1,b)+b;
It calls the recur function each time decreasing the value of 3 in 3x2 and adding a 2 to the same.
Graphically it goes on like this
mul=recur(3,2) //If we pass 3 and 2 in the func. call.
=recur(2,2)+2
=recur(1,2)+2+2
=recur(0,2)+2+2 +2
=0+2+2+2
Isn't it same as
3 X 2
= 2 X 2 +2
=1 X 2 + 2 + 2
=0 X 2 +2 + 2 + 2
=2+2+2
=6
But the job it not complete now.
The upward movei.e. bottom-up [NOT LITERALY MEANING UPWARD]
What has happened internally is that
In the STACK memory of the computer ram each step of the above lines are stacked one by one.
The line mul=recur(a-1,b)+b; stacks each iteration in stackes untill the value of a decreases to 0.
when 0 is hit it is returned which acts as an exit criteria and indicates the program execution to de-stack the stack(unloading of the stack).
RECURSION decoded
1.HENCE RECURSION IS THE PROCESS OF CALLING THE SAME FUNCTION INSIDE ITSELF.
2. THE FUNCTION ON EACH ITERATION KEEPS EACH EXPRESSIONS IN THE STACK.
3. WHEN THE return 0; IS HIT THE STACK IS UNLAODED AND EXECUTED TO GET THE SOLUTION.
Finally i got what i was seraching for...The total insight on Recursion...
How it flows in a program...how it stacks ad unstacks and operates.
Let us begin.
Let us perform a recursive programming for finding the multiplication of two numbers.
NOTE: i chose this task as it is a bit ahead in class of the factorial recursion and behind the fibonacci series generation....
THEORY
Basic of multiplication is that we want to add a relatively larger series of same number.
i.e. 2+2+2+2+2+2+2+2 +2+2
Gosh it was boring and hectic to type it…see !
So we multiply.
No. of 2s multiplied by 2 i.e. 10X2=20
Note: I took 10X2 and not 2X10 because it fits in to my recursive program which is coming ahead. Theres absolutely no problem and the program needs just a minor change if you wanna do it the other way round. For now lets go on with what I say…
The Recursive Multiplication
To perform the above multiplication operation we use recursion.
As in factorial we shred the number by factor of 1 in each run of the function similary we will have two numbers to multiply , let us suppose3 and 2.
3 will be shreded in each step and will be added to 2 like in
3 X 2
= 2 X 2 +2
=1 X 2 + 2 + 2
=0 X 2 +2 + 2 + 2
=2+2+2
=6
Now we need to convert this mathematical idea into an expression which on running each step shall give us the corresponding mathematical steps
Try thinking a bit for a function…
The line 3x2=2x2+2 can best help one…It helped me !
The equivalent expression of above is
Mul= (a-1)*b+b;
But its not the expression which can be put into our recurvie function.
We wil advance and reach to the concept…trust me !
THE CONCEPTwith the multiplication question
Now let us look at the core concept of recursion and the insight of the operation.
Look at the following code as it does the multiplication operation …and I’l tell u why and how !
int recur(int a,int b)
{
if(a==0)
return 0;
else
{mul=recur(a-1,b)+b; // let this line be refered as Line A.
return mul;
}
}
The line A is the master line which does our multiplication operation.
The downward move
mul=recur(a-1,b)+b;
It calls the recur function each time decreasing the value of 3 in 3x2 and adding a 2 to the same.
Graphically it goes on like this
mul=recur(3,2) //If we pass 3 and 2 in the func. call.
=recur(2,2)+2
=recur(1,2)+2+2
=recur(0,2)+2+2 +2
=0+2+2+2
Isn't it same as
3 X 2
= 2 X 2 +2
=1 X 2 + 2 + 2
=0 X 2 +2 + 2 + 2
=2+2+2
=6
But the job it not complete now.
The upward movei.e. bottom-up [NOT LITERALY MEANING UPWARD]
What has happened internally is that
In the STACK memory of the computer ram each step of the above lines are stacked one by one.
The line mul=recur(a-1,b)+b; stacks each iteration in stackes untill the value of a decreases to 0.
when 0 is hit it is returned which acts as an exit criteria and indicates the program execution to de-stack the stack(unloading of the stack).
RECURSION decoded
1.HENCE RECURSION IS THE PROCESS OF CALLING THE SAME FUNCTION INSIDE ITSELF.
2. THE FUNCTION ON EACH ITERATION KEEPS EACH EXPRESSIONS IN THE STACK.
3. WHEN THE return 0; IS HIT THE STACK IS UNLAODED AND EXECUTED TO GET THE SOLUTION.
Comment