C++ recursion help? I don't get this T_T?

Question

right now i'm learning about recursion but my teacher doesn't explain it so i understand it...... can anyone explain it step by step? I get that while the condition is false, the program will go to the return at the end of the program update the value and then start over with that value............ but i dont get like after it finishes stacking, it unstacks and what calculations are being made..... here's the function i'm having trouple with:

int m9(int num)
{
if (num>=20)
return -5;
return m9(num+4)+2*num;
}
int main()
{
cout << m9(15) << endl;
return 0;
}




if anyone could help me better understand this it would be deeply appreciated thanks

Answer 1

Think of it this way, the function keeps calling itself. That is what recursion is all about. We will evaluate this problem one step at a time.



As long as num is less than or equal to 20, we can say that m9(num) = m9(num+4)+2*num. Look at the following, and read the explanations below:



m9(15)



= m9(15+4) + 2*15 (eqn. 1)



= [ m9( {15+4} +4) + 2*{15+4} ] + 2*15 (eqn. 2)



= [ { -5 } + 2*{15+4} ] + 2*15 (eqn. 3)



= [ 33 ] + 2*15 (eqn. 4)



= 63



(eqn. 1) I have expanded m9(15) to m9(15+4)+ 2*15. Since I cannot reach an answer until I know what m9(15+4) evaluates to, I have to evaluate it next.



(eqn. 2) I expand m9(15+4) the same way I expanded m9(15) the first time, giving me m9( {15+4]} +4) which I placed in square brackets because that is the part that we are working with right now. We will ignore the 2*15, because the new instance of m9 that we just called does not know anything about it; it only knows about what is inside of the square brackets. We still cannot evaluate what is inside of the square brackets until we have evaluated m9( {15+4} +4), so we do that next.



(eqn. 3) Luckily we know that m9( {15+4} +4) is m9(23), and since 23 is greater than 20, we have reached the base case, and we return a -5.



(eqn. 4) Now we know everything we need to know to evaluate what is inside of the square brackets, because they are all integer values, and they give us 33, which we return to the previous call.



(eqn. 5) Now we know everything we need to know to evaluate the rest.



The idea of recursion is this: I don't know the answer of problem A until I solve problem B, which is a variation of type A. I can't solve problem B until I solve problem C, and C is a variation of A also. This chain continues until we get down to the base case. Once we reach the base case we can solve the rest of the equations as we work backwards to where we came from.



This is not the only way to use recursion, but it is a common one, and it is what is used here. Hopefully that gives you a better idea of what is going on at least. Pardon the ugly formatting, it is really hard to communicate mathematical ideas in such a limited text environment.



Also, I just want to add my two bits: recursion is definitely very important in programming. There are TYPES of programming that never really need recursion, but it has tons of uses in everything from database management to game programming. One of the most commonly used applications of recursion are binary trees. Granted, some binary trees can be built using loops, but the result is usually quite messy.



My advice: if you want to take programming seriously, learn ALL of the different techniques and strategies that are used commonly, then decide for yourself what is useful to you.

Answer 2

Ok what you have to understand about programming first is that , the compiler executes the commands line by line.

So lets go to the first line (we assume that num is 15 from the main method because the main method executes first befor any other line of code in the program)

first if statement shows that 15 is not >=20, so we should go to

return m9(num+4)+2*num;

this will try 15+4=19 in the m9 method.

this will check is 19>=20 or not

since the answer is not we should again check

if 19+4=23 <=20 which is correct.

since it is correct the -5 is send back to

return m9(num+4)+2*num; which becomes -5+2*19=34;

now we have to send it back to the first call where we get

return m9(num+4)+2*num; = 34+2*15=64;



The best way to learn this is by try debuggin this code in visual studio or similar IDE's you can see what happens after each steps in debugging....

Answer 3

Here's how the recursion will unroll:

go to m9 with arg 15 (A)

>go to m9 with arg 19 (B)

>>go to m9 with arg 23 (C)

>>>return -5 as result for C [-5]

>>return result from C + 2*argB as result for B [33]

>return result from B + 2*argA as result for A [63]

cout result for A ["63"]



Recursion is -NOT- the same thing as a loop. While you can transform any loop into a recursive function, you cannot easily transform all recursive functions into a loop. This is due to the fact that you can have multiple calls to the recursive function within itself. For example:



int treeSum(node *n){

if(n==0) return 0;

return n->value + treeSum(n->left) + treeSum(n->right);

}



re [J] a [Y]: just because recursion is difficult to understand doesn't mean you should pass it off as something useless. Some of the most elegant and efficient algorithms use recursion, and many of them would otherwise be awful in iterative form. I challenge you to develop an efficient iterative solution to the above treeSum() function.

Answer 4

recursion is the process of a function calling itself. A simple example:



void recur()

{

if(condition)

{

recur()

}

}



basically the purpose of recursion is to perform a similar function as to looping, but looping is more efficient in my opinion for two reasons:



1. Loops are much easier to follow than recurring functions, and easier to understand.



2. Recurring functions result in spaghetti code.



3. Loops are more efficient at run time since recursion adds the overhead of an extra function call for each iteration.



As for the functionality of your function:



if num >=20 then your function will return -5.

if not, then it will return another value calculated by running the same function a few more times. The process could be simplified quite a lot by using loops, though teachers still want you to understand recursion for pedagocial purposes, even if you will never use them.



I've been developing for 5 years now and I've never used recursion once.