-
Recursions
Hello, i took a test and had a problem with a function. I was wondering if someone could possibly explain the correct way of finding the answer. I have a final exam on this tomorrow and am still very confused! thanks for the help guys
Code:
for the function of p below, give the output of the call p(5)
void p( int x)
{
if (x<=0) return;
if (x%2==0) cout <<x<<endl;
p(x-1);
if (x%2 !=0) cout x<<endl;
}
for the function p below give the output of the call p(3)
void p (int x)
{
cout <<x<<endl;
if (x> 0) {p(x-1);p(x-1);}
}
for the first one i got only 5 but itshould be 4 2 1 3 5 and i have no idea how to figure that out
the second one should be 321001002100100
if any of you can explain how this concept works i would greatly appreciate it
-
Just follow the flow of the program and write down each step.
I'll start with the first one.
Call p with x = 5
If x < 0 return (5 < 0 is false so don't return)
If x % 2 == 0 then output x (5 % 2 is 1 so don't output 5)
Call p with new x = current x - 1 (in other words call p with x = 4)
If x < 0 return (4 < 0 is false so don't return)
If x % 2 == 0 then output x (4 % 2 is 0 so output 4)
... and so on
-
i am starting to understand the first part of it going from 4 3 ect i dont understand how it goes back up? i figured once u got to a lower number like that it cant have an output of 5 at the end. the second one i am not understanding at all.. the first one i am seeing it more clearly
-
It goes back up as the call stack unwinds because your function prints old values of x before it calls p again and also before it returns.
-
>> i dont understand how it goes back up?
Post your step by step. What happens after you execute a return?
>> the second one i am not understanding at all..
Post your step by step like I did. It will be easier to help you understand where you are confused.
-
i will help a little since i can understand iterative ways better than recursive ones
#1
Code:
void p( int x) {
while (x>0) {
if (x%2 == 0) cout << x << endl;
--x;
if (x%2 != 0) cout << x << endl;
}
}
-
But iteration just has one function call, recursion has several.
The problem is that in recursion, when the function calls itself, it doesn't jump to top. Instead, a new function of the same type is generated you might say, and this new one starts from the top and goes down. When that new function is done, it goes back to the old one again.
Hope that gives some insights into the whole. Try running a debugger or writing it down on a paper and it might make some more sense.