Hi,
I am trying to find out the output of following recursive program using tracing:
int call(int num){
int x=1;
int y=0;
if(num>0){
x=x+num-1;
y=call(num-1)+2;
}
return x;
}

I have done following (replacing call( ) by c( ) for ease of typing):
c(5)
=> x=5 & y=c(4) +2
=> x=4 & y=c(3) +2 +2
=> x=3 & y=c(2) +2+2+2
=> x=2 & y=c(1)+2+2+2+2
=> x=1 & y=c(0)+2+2+2+2+2
So it should be 1. But the answer is not correct. Can somebody please guide me.

Zulfi.

 

you call call function inside the call function...

 

you call call function inside the call function...

Hence why it is a "recursive" function.

 

Hi,
I am trying to find out the output of following recursive program using tracing:
int call(int num){
int x=1;
int y=0;
if(num>0){
x=x+num-1;
y=call(num-1)+2;
}
return x;
}

I have done following (replacing call( ) by c( ) for ease of typing):
c(5)
=> x=5 & y=c(4) +2
=> x=4 & y=c(3) +2 +2
=> x=3 & y=c(2) +2+2+2
=> x=2 & y=c(1)+2+2+2+2
=> x=1 & y=c(0)+2+2+2+2+2
So it should be 1. But the answer is not correct. Can somebody please guide me.

Zulfi.

I get that the return value should be 5.

Remember, it's recursive -- so you can't just take the return value of the last invocation. You need the return value of the first invocation.

 

Hence why it is a "recursive" function.

um... wouldn't you calculate the value, return it to main, then send it to call function, recalculate it, get the new value, return it to main, then send it to call function, recalculate it....

 

um... wouldn't you calculate the value, return it to main, then send it to call function, recalculate it, get the new value, return it to main, then send it to call function, recalculate it....

No. A recursive function calls itself (either directly or indirectly). For instance, you might implement the factorial function (ignoring illegal inputs) as

int factorial(int n)
{
   return n? n * factorial(n - 1) : 1;
}

If your main calls factorial(12), then the factorial function will call factorial(11), which will call factorial(10), and so on until finally factorial(0) is called, which will return a value of 1 to the call to factorial just before it, which can no calculated a return value and pass that back to the factorial function that was called just before that. Eventually the first call to factorial gets a value back from the recursive call it made and it can finally return the overall value.

 

Hi,
Thanks for your reply:

I get that the return value should be 5.

Remember, it's recursive -- so you can't just take the return value of the last invocation. You need the return value of the first invocation.

Okay, it would do backtracking. This is important quality of recursive functions.
At call(0) it would start returning value (because return statement was not executed due to recursive call for arguments, 5, 4, 3, 2, 1),it would first return 0, then it would again execute return 1 for call(1) and then 2 for call(2) and so on until it would return 5 for call 5.

Where these return values for call(0), call(1).... call(4) would go?

This is my code for Java??

import javax.swing.*;

public class recursionOut5{

public static void main(String[ ] args) {
int k= call(4);
JOptionPane.showMessageDialog(null, k);
}
static int call(int num){
int x=1;
int y=0;
if(num>0){
x=x+num-1;
y=call(num-1)+2;
}
return x;
}

}

The program is giving 5. But please remove my confusion.
You gave me following answer:
<
so you can't just take the return value of the last invocation. You need the return value of the first invocation.
>
But guide me about the fate of other return calls.

Zulfi.

 

The program is giving 5. But please remove my confusion.
You gave me following answer:
<
so you can't just take the return value of the last invocation. You need the return value of the first invocation.
>
But guide me about the fate of other return calls.

They were used by the function that called them -- no different than anything else.

If you have a function bob() that has a statement x = 2 * sue(), then sue() is called, computes a value, and returns that value to that place in the calling function at which point the calling function uses the return value to evaluate that expression and assign the result to the variable x. It is absolutely, completely, and totally no different (in almost all languages) if sue() happens to be bob(). The function bob() is called and it returns a value that is then used by a different invocation of bob() to assign a value to a local variable.

Remember, whenever a function is called, recursively or not, that function is given space on the stack and has its own local variables. So if there are 20 calls to bob() that are active, there are 20 different local variables called x, one for each active invocation. At any given moment in time, only the function (be it bob() or some other function) on the top of the stack is actually running.

 

They were used by the function that called them -- no different than anything else.

If you have a function bob() that has a statement x = 2 * sue(), then sue() is called, computes a value, and returns that value to that place in the calling function at which point the calling function uses the return value to evaluate that expression and assign the result to the variable x. It is absolutely, completely, and totally no different (in almost all languages) if sue() happens to be bob(). The function bob() is called and it returns a value that is then used by a different invocation of bob() to assign a value to a local variable.

Remember, whenever a function is called, recursively or not, that function is given space on the stack and has its own local variables. So if there are 20 calls to bob() that are active, there are 20 different local variables called x, one for each active invocation. At any given moment in time, only the function (be it bob() or some other function) on the top of the stack is actually running.

 

Hi,
Thanks my friend for your continuous reply.
<
They were used by the function that called them -
>
No they are not used. Because if the calling function was using them, it should have displayed the values. Its only displaying 5 and this is the result you told me. Its something similar to what you said earlier:
<Remember, it's recursive -- so you can't just take the return value of the last invocation. You need the return value of the first invocation.>

Zulfi.

 

Why should it have displayed the values of each one? Your program only displays the value returned by the first invocation.

Put a print statement within the definition of call() that prints num, x, and y. In fact, put it in there twice, once before the if() statement and once after.