How to visualize recursion

Question

I am trying to understand recursion in Java by visualizing it. I have gone through some tutorials on youtube and using the below example from one of them

public class TestRecursion {

    public static void main(String []args) {
        new TestRecursion().reduceByOne(10);
    }

    public void reduceByOne(int n) {
        System.out.println("Before "+n);
        if(n >= 0) {
            reduceByOne(n-1);
            System.out.println("Inside "+n);
        }
        System.out.println("After "+n);
    }
}

From what I have understood so far, every call to reduceByOne() would be placed in the execution stack. Something like

So, first main() gets on the stack. Since it calls reduceByOne(10), this method will get onto the stack which would then call reduceByOne(9) and push that to stack and so on. After reduceByOne(-1) is pushed onto the stack, since there are no more methods to execute, reduceByOne(-1) would be popped and executed.

I am having trouble understanding what happens once the method is popped? Lets, says, reduceByOne(2) is popped from the stack. I believe, the code that would be executed would look something like this

public void reduceByOne(2) {
        System.out.println("Before "+2);
        if(2 >= 0) {
            reduceByOne(2-1);
            System.out.println("Inside "+2);
        }
        System.out.println("After "+2);
    }

Wouldn't this put reduceByOne(2-1) again onto the stack? Or would it be skipped? If so, how does the runtime know what to execute and what to skip once the method is popped?

May be I am complicating it too much. However, I am not able to get a clear understanding of recursion so any help is much appreciated.

Answer 1

When the method returns (in your case that will first occur when n >= 0), the execution will be returned to the previous "call" point, in this case, the next line to be executed would be System.out.println("Inside "+n);, after which each method would then be proceeded to exit and returned to the previous "call" point in the code

For example...

Green been the "push" and the orange been the result of the "pop"

Obviously, at some point, you'll return to main, but this is just an illustration

This is not different than how a "normal" code works, you call a method, when it returns, it returns to the point that it was executed previously

This is an oversimplification of the process, but I hope it allows you to better visualize the process

Answer 2

I will explain what happens when the recursion occurs using your example. As you know the method which is on top of the stack gets executed and get popped out. This explanation is just for understanding purpose.

You have confused with the idea when method/method state is pushed and popped from the stack.

public static void main(String []args) {
    new TestRecursion().reduceByOne(10); //first line
}

Main method get on top of the stack.

Stack -> main()

Now as the first line encounters it calls reduceByOne(10). So that gets added to the stack.

Stack -> reduceByOne(10) main()

As reduceByOne(10) is on top of the stack,execution of main() pauses, and execution of reduceByOne(10) starts. As the execution of line

reduceByOne(n-1);

Another method call occurs and its pushed to stack. So current method pauses execution because reduceByOne(9) is now on top of stack.

Stack -> reduceByOne(9) reduceByOne(10) main()

Similarly stacks gets added with method states.

Stack -> reduceByOne(-1) --- reduceByOne(9) reduceByOne(10) main()

When reduceByOne(-1); is executed, if condition in the method fails.

if(n >= 0) { // now n is -1
    reduceByOne(n-1);
    System.out.println("Inside "+n);
}

And it completes the execution, reduceByOne(-1) gets popped out. Now reduceByOne(0) resumes execution from the line

...
System.out.println("Inside "+n); // ---- line(1)
    }
    System.out.println("After "+n);
}

and gets popped out. Now reduceByOne(1) resumes execution from line(1) as gets popped out. Now reduceByOne(2) is on top of the stack, it resumes its execution from line(1). Similarly it comes back upto reduceByOne(10). And now reduceByOne(10) completes execution resuming from line(1) and gets popped out. Now only main method remains in the stack. It also gets executed and popped out. Thus execution terminates.

Answer 3

You may use fractals to visualize it. You can put some waiting points(sleep), so you can watch it. It helped me once. i.e.

public class FractalTree extends JFrame {
public FractalTree() {
    setLocation(500, 50);
    setSize(800, 700);
    setTitle("Fractal Tree");
    setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    add(new TreePanel());
    //add(new MyCanvas());
    setVisible(true);
}

public static void main(String[] args) {
    // TODO Auto-generated method stub

    // initialize screen elements
    FractalTree ft = new FractalTree();

}

}


class TreePanel extends JPanel {
private static int maxLength = 10;;

public void drawFractalTree(Graphics g, int x1, int y1, double angle, int level) {
    if (level <= 0)
        return;
    //

    int x2 = x1 + (int) (Math.cos(Math.toRadians(angle)) * level * maxLength);
    int y2 = y1 + (int) (Math.sin(Math.toRadians(angle)) * level * maxLength);

    // set color
    setLineColor(g, level);
    // draw between two points
    g.drawLine(x1, y1, x2, y2);


    try {
        TimeUnit.SECONDS.sleep(1);
    } catch (InterruptedException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }


    // call rec.
    drawFractalTree(g, x2, y2, angle - 20, level - 1);
    drawFractalTree(g, x2, y2, angle, level - 1);
    drawFractalTree(g, x2, y2, angle + 20, level - 1);

}

@Override
public void paintComponent(Graphics g) {
    super.paintComponent(g);
    g.setColor(Color.WHITE);
    g.fillRect(0, 0, 800, 700);
    drawFractalTree(g, 400, 500, -90, 9);
}

public void setLineColor(Graphics g, int i) {
    switch (i) {

    case 1:
        g.setColor(Color.GREEN);
        break;
    case 2:
        g.setColor(Color.YELLOW);
        break;
    case 3:
        g.setColor(Color.ORANGE);
        break;
    case 4:
        g.setColor(Color.CYAN);
        break;
    case 5:
        g.setColor(Color.MAGENTA);
        break;
    case 6:
        g.setColor(Color.PINK);
        break;
    case 7:
        g.setColor(Color.RED);
        break;
    case 8:
        g.setColor(Color.BLUE);
        break;
    case 9:
        g.setColor(Color.GRAY);
        break;
    default:
        g.setColor(Color.BLACK);
        break;
    }
}
}