# Is there a way to display the stack during recursion method?

I'm trying to learn recursion. I copied this bit of code from my book and added the displays to help me trace what the method is doing and when.

``````public static void main(String[] args) {

System.out.println(sum(4));

}//main

public static int sum(int n) {
int sum;
System.out.println("n = " + n + "\n");
if (n == 1)
sum = 1;
else
sum = sum(n - 1) + n;
System.out.println("n after function = " + n + "\n");
System.out.println("sum after function = " + sum + "\n");
return sum;
}
``````

Here's the results:

n = 4

n = 3

n = 2

n = 1

n after function = 1

sum after function = 1

n after function = 2

sum after function = 3

n after function = 3

sum after function = 6

n after function = 4

sum after function = 10

10

I'm getting hung up on what's being stored in the stack, or perhaps how it's being stored.

Is there a way to display what's in the stack while n is counting down to 1?

This is an odd concept - it's like an invisible loop storing values in a way I don't understand.

## 4 Answers

You cannot access the stack contents directly from your Java code, but if you use a debugger (which is integrated in every modern IDE) you get something even better: it will list the stack of method calls and for each level, if you select it, the values of the local variables on the stack.

• Actually you can access the stack trace directly. See stackoverflow.com/questions/1069066/…. Still using a debugger is the proper answer. – msell Dec 23 '12 at 7:15
• @msell: that method does not give access to variables, though. – Michael Borgwardt Dec 23 '12 at 14:24
• I'll definitely check out the debugger tutorial! Thanks for the info. – MayNotBe Dec 23 '12 at 22:23
• Downgraded because answer is not correct. See comment by @msell – vainolo Dec 24 '12 at 8:30
• @vainolo: how about actually reading the question before voting on an answer? OP wants to look at the contents on the stack. You cannot do that using getStackTrace(). So my answer is correct. – Michael Borgwardt Dec 24 '12 at 8:57

You can use a debugger like eclipse to view the stack at any given time, but trying to envision recursion as a loop isn't the best way to understand it. As you go down the stack, you break off small pieces of the problem, until you get to the bottom of the stack, where the problem is trivial to solve. Then as you go back up the stack, you put the pieces back together again.

``````sum(4)
sum(3) + 4
sum(2) + 3
sum(1) + 2
1
``````

`sum(4)` is broken down into `sum(3) + 4`. `sum(3)` is broken down into `sum(2) + 3`. Eventually you get to `sum(1)`, which has a trivial answer of `1` (the first choice in your `if` statement).

There's no possible way to break it down further, so you go back up the stack, adding `2`, `3`, and `4`. It's a ride down and up the stack, a very different thing from a loop, even though they can accomplish the same calculation.

You can access the stack, but not the values on the stack.

``````public class StackTrace {

public static void main(String[] args) {
recurse(10);
}

static void recurse(int depth) {
for (StackTraceElement each: new Exception().getStackTrace()) System.out.println(each);
if (depth > 0) recurse(depth - 1);
}

}
``````

Of course we could also write a program that maintains its own, C style, stack, where we push all arguments and locals and return values on the stack

``````public class Main {

public static void main(String[] args) {
new Main().run();
}

int[] stack = new int;
int base = 0;

public void run() {

// push arguments on stack
stack[base] = 4;
// increase base pointer and call method
base += 1;
call();
// retrieve result
int result = stack[base];
// print it
System.out.println(result);

}

public void call() {
// push locals on stack and increase base, now arg n
// is at base - 2 and local sum is at base - 1
stack[base] = 0;
base += 1;
// test if n equals 1
if (stack[base - 2] == 1) {
// if yes set sum to 1
stack[base - 1] = 1;
} else {
// push new argument on stack
stack[base] = stack[base - 2] - 1;
// increase base pointer and call method
base += 1;
call();
// add result to sum
stack[base - 1] += stack[base];
// add n to sum
stack[base - 1] += stack[base - 2];
}
// cache return value
int result = stack[base - 1];
// decrease base pointer by size of both args and locals
base -= 2;
// push result on stack
stack[base] = result;
}
}
``````

the programs uses the calling convention that callers are responsible for pushing arguments and increasing the base pointers, and receivers are responsible for resetting the base pointer and leaving a return value on the stack.

This is how method calls happen at the machine level.