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

Question

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.

Answer 1

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.

Here's a tutorial on how to use the debugger in eclipse.

• msell: Actually you can access the stack trace directly. See stackoverflow.com/questions/1069066/…. Still using a debugger is the proper answer.
• Michael Borgwardt: @msell: that method does not give access to variables, though.
• MayNotBe: I'll definitely check out the debugger tutorial! Thanks for the info.
• vainolo: Downgraded because answer is not correct. See comment by @msell
• Michael Borgwardt: @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.

Answer 2

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.

Answer 3

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);
 }
}

Answer 4

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[100];
 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.