Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question

4 Answers 4

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.

share|improve this answer
2  
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
2  
@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.

share|improve this answer
    
That's a great way to visualize it! Thanks. –  MayNotBe Dec 23 '12 at 22:22

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

}
share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.