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.
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.
5
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.
0
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[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.