Can someone please explain to me why this prints out 1 2 3 4 5? I figured it would print out 4 3 2 1 0 but my book and eclipse both say I'm wrong.
public class whatever {
/**
* @param args
*/
public static void main(String[] args) {
xMethod(5);
}
public static void xMethod(int n){
if (n>0){
xMethod(n-1);
System.out.print(n + " ");
}
}
}
It is pretty simple, these are the calls
main
xMethod(5)
xMethod(4)
xMethod(3)
xMethod(2)
xMethod(1)
xMethod(0)
print 1
print 2
print 3
print 4
print 5
So you see the prints are 1,2,3,4,5
xMethod returns, the next-to-innermost call will start right back where it left off: right after the call to itself, at the print.
xMethod(n) returns there is a print statement System.out.print(n+" "), then the level returns to the upper level that called it, and it prints its value, so on until the main level is reached and the program ends.if statement is called the stop condition, otherwise the recursion would go on forever with negative values. When n reaches 0 the recursion starts to go back to its callers.It's the result of the call stack. Here's what it would look like after a call with n = 5. Rotate your head about 180 degrees, since the bottom of this call chain is actually the top of the stack.
In a recursive call, you have two cases - a base case and a recursive case. The base case here is when n == 0, and no further recursion occurs.
Now, what happens when we start coming back from those calls? That is, what takes place after the recursive step? We start doing System.out.print(). Since there's a condition which prevents both recursion and printing when n == 0, we neither recurse nor print.
So, the reason that you get 1 2 3 4 5 as output is due to the way the calls are being popped from the stack.
It first call itself recursively and only when the recursive call finishes it prints. So think about which call finishes first - it's when n = 0. Then n = 1, etc.
It's a stack and you print after taking from the stack (after the recursion call), so the order is reversed. If you printed before putting on the stack, then the order is preserved.
System.out.print(n + " ");
xMethod(n-1);
It will print 5 4 3 2 1. Because It will first print then call xMethod.
And in your case
xMethod(n-1);
System.out.print(n + " ");
Here it will reach to end condition then poped up and print. so 1 2 3 4 5
To explain how recursion works, let's see the sample of factorial calculation:
int factorial(int i) {
if (i == 0) {
return 1;
}
return i * factorial(i - 1);
}
For example let's get factorial value of 5:
int result = factorial(5);
Remember that exit value:
if (i == 0) {
return 1;
}
and return value:
i * factorial(i - 1)
Just look at iterations (according to return value):
5*factorial(4) -> 4*factorial(3) -> 3*factorial(2) -> 2*factorial(1) -> 1*factorial(0)
In fact it is:
5*(4*(3*(2*(1*factorial(0)))))
cause factorial(4) == 4*factorial(3), factorial(3) == 3*factorial(2), etc.
last iteration is factorial(0) that equals 1 (look at exit value).
In result:
5*(4*(3*(2*(1*1)))) = 120
xMethod is called until n is 0. The stack will then be xMethod(5)->xMethod(4)->xMethod(3)->xMethod(2)->xMethod(1)->xMethod(0). As it finishes xMethod(0), it will pop into the next line in xMethod(1), printing 1. This will then repeat until xMethod(5) is exited.
If you went and expanded each xMethod as it was called, the code would look something like this:
{
nA = 5 // What n was set at first
if (nA>0){
{
// Instead of xMethod(n-1),
// we're setting nB to nA - 1 and
// running through it again.
nB = nA - 1 // nB is 4
if (nB>0){
{
nC = nB - 1 // nC is 3
if (nC>0){
{
nD = nC - 1 // nD is 2
if (nD>0){
{
nE = nD - 1 // nE is 1
if (nE>0){
{
nF = nE - 1 // nF is 0.
if (nF>0){
// This will never execute b/c nF is 0.
}
}
System.out.print(nE + " "); // prints 1
}
}
System.out.print(nD + " "); // prints 2
}
}
System.out.print(nC + " "); // prints 3
}
}
System.out.print(nB + " "); //prints 4
}
}
System.out.print(nA + " "); //prints 5
}
}
1 public static void xMethod(int n){
2 if (n>0){ //the base condition
3 xMethod(n-1); //function is again called with one value less than previous
4 System.out.print(n + " "); //now print
5 }
6 }
Now look at line#3, As nothing is printed but the function is again called, so from line#3, the call reaches to line#1 again. which means, n was 5, but the new call takes n = 4 and it keeps going till line#2 tells that n is now less than 0.
When if condition fails at line#2, it reaches at line#5 and then line#6 which means the function has ended execution, and n = 1 at this time.
Now where should the call be returned? at line#3 where the last function was called and it will be popped out from stack executing line#4 which prints the value of n i.e. 1 2 3 4 5.
this xMethod(n-1); System.out.print(n + " ");
should be:
System.out.print(n + " ");
xMethod(n-1);
