# Output of Recursive Program 2

#### zulfi100

Joined Jun 7, 2012
656
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.

#### shteii01

Joined Feb 19, 2010
4,644
you call call function inside the call function...

#### WBahn

Joined Mar 31, 2012
26,398
you call call function inside the call function...
Hence why it is a "recursive" function.

#### WBahn

Joined Mar 31, 2012
26,398
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.

#### shteii01

Joined Feb 19, 2010
4,644
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....

#### WBahn

Joined Mar 31, 2012
26,398
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

Code:
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.

#### zulfi100

Joined Jun 7, 2012
656
Hi,
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.
<
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.

#### WBahn

Joined Mar 31, 2012
26,398
The program is giving 5. But please remove my confusion.
<
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.

#### zulfi100

Joined Jun 7, 2012
656
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.

#### zulfi100

Joined Jun 7, 2012
656
Hi,
<
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.

#### WBahn

Joined Mar 31, 2012
26,398
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.