How to trace recursion questions.

[Daniel Gen Li]

For a question like this:

public static void doSomething(int n){
    if (n > 0){
        doSomething(n-1);
        System.out.print(n * 2);
        doSomething(n-1);
    }
}

The problem may ask something like what this code will output if you call doSomething(5).

I'm learning recursion right now, and I find it really hard tracing the execution of these questions. Are there any techniques on doing these questions? Because I'm looking at some of these questions on previous AP exams and it takes me around 5 mins just to do one and I sometimes get lost on which recursive call I'm at. Especially the ones that made more than recursive call, they are really confusing. I usually don't have this much trouble with programming...

any help is greatly appreciated...

[Mike Simmons]

Well, for this particular problem, you might try looking at it from the other direction. That is, you can see that it starts with doSomething(5) , then calls doSomething(4), then doSometing(3) etc down to doSomething(0). Try looking at those in the reverse order.

What does doSomething(0) do?

What does doSomething(1) do?

What does doSomething(2) do?

And so on.

A pattern should start to emerge. Such patterns can be much easier to understand if you start with small parts of the pattern, before trying to understand the whole thing.

[David Newton]

I've also just printed out execution traces, increasing the indent each level:

Enter fact(6)
    Enter fact(5)
        Enter fact(4)
            Enter fact(3)
                Enter fact(2)
                    Enter fact(1)
                        Enter fact(0)
                        0!Ret: 1
                    Ret: 1 * fact(n-1) = 1 * fact(0) = 1 * 1 = 1
                Ret: 2 * fact(n-1) = 2 * fact(1) = 2 * 1 = 2
            Ret: 3 * fact(n-1) = 3 * fact(2) = 3 * 2 = 6
        Ret: 4 * fact(n-1) = 4 * fact(3) = 4 * 6 = 24
    Ret: 5 * fact(n-1) = 5 * fact(4) = 5 * 24 = 120
Ret: 6 * fact(n-1) = 6 * fact(5) = 6 * 120 = 720
fact(6) = 720

In the end it's the same thing as what Mike's saying, but indent-ier.

And if you turn the output on its side it's a graph of how awesome it is.

[salvin francis]

hi David Newton

You have probably printed out the execution trace of a different program(than the OP) here.
Also I do feel that it will be difficult to show in text the execution of

doSomething(n-1);  
System.out.print(n * 2);  
doSomething(n-1);  

since it contains two recursive calls to same functions before and after a line of code.


do correct me if i am wrong:

n=3

doSomething(3)
	doSomething(2)
		doSomething(1);
			doSomething(0);
			print 2
			doSomething(0);
		print 4
		doSomething(1);
			doSomething(0);
			print 2
			doSomething(0);
	print 6
	doSomething(2)
		doSomething(1);
			doSomething(0);
			print 2
			doSomething(0);
		print 4
		doSomething(1);
			doSomething(0);
			print 2
			doSomething(0);

[David Newton]

salvin francis wrote:You have probably printed out the execution trace of a different program(than the OP) here.

Well, yes, a factorial. Otherwise I'd be giving away too much specific info.

lso I do feel that it will be difficult to show in text the execution of [...]

I agree it's more complicated, but for people that are more visual, it can be really helpful. It took me these kinds of traces, along with some boxes to indicate nesting, to understand how recursion works. Not everybody might need such a tool, or it may be more confusing than helpful for some.

The Size of the Tree is: 4
Enter inOrder(BstNode@6e3d60 word=dove [left=BstNode@17fa65e, right=BstNode@18385e3]): 
    > Calling inOrder.getRight(BstNode@18385e3)...
    Enter inOrder(BstNode@18385e3 word=aardvark [left=null, right=null]): 
        > Calling inOrder.getRight(null)...
        Enter inOrder(null): 
            < Node is null, returning ''
        > Adding on current node value 'aardvark'
        > Calling inOrder.getLeft(null)...
        Enter inOrder(null): 
            < Node is null, returning ''
        < Returning ' aardvark '
    > Adding on current node value 'dove'
    > Calling inOrder.getLeft(BstNode@17fa65e)...
    Enter inOrder(BstNode@17fa65e word=melon [left=null, right=BstNode@1cb25f1]): 
        > Calling inOrder.getRight(BstNode@1cb25f1)...
        Enter inOrder(BstNode@1cb25f1 word=foo [left=null, right=null]): 
            > Calling inOrder.getRight(null)...
            Enter inOrder(null): 
                < Node is null, returning ''
            > Adding on current node value 'foo'
            > Calling inOrder.getLeft(null)...
            Enter inOrder(null): 
                < Node is null, returning ''
            < Returning ' foo '
        > Adding on current node value 'melon'
        > Calling inOrder.getLeft(null)...
        Enter inOrder(null): 
            < Node is null, returning ''
        < Returning ' foo  melon '
    < Returning ' aardvark  dove  foo  melon '
The Tree elements in order: 
 aardvark  dove  foo  melon 

To me, that's pretty noisy, but if I read it line-by-line, and I include a reference tree of the graph, I'm usually all set.

(And you'll notice my implementation is a little "backwards"

[salvin francis]

This gives a better idea

To be honest, I wasnt able to understand that output at all !!!
how do you make sense of such gibbrish !!

[David Newton]

Once there are boxes around the levels it's the same thing. It would have been just as easy to create GraphViz output (or whatever) to get a pretty picture :)

[salvin francis]

By the way, I took a lot of effort to design that....

OP ! i hope that helps you

[Chester Saddlemeyer]

David Newton wrote:I've also just printed out execution traces, increasing the indent each level:

Enter fact(6)
    Enter fact(5)
        Enter fact(4)
            Enter fact(3)
                Enter fact(2)
                    Enter fact(1)
                        Enter fact(0)
                        0!Ret: 1
                    Ret: 1 * fact(n-1) = 1 * fact(0) = 1 * 1 = 1
                Ret: 2 * fact(n-1) = 2 * fact(1) = 2 * 1 = 2
            Ret: 3 * fact(n-1) = 3 * fact(2) = 3 * 2 = 6
        Ret: 4 * fact(n-1) = 4 * fact(3) = 4 * 6 = 24
    Ret: 5 * fact(n-1) = 5 * fact(4) = 5 * 24 = 120
Ret: 6 * fact(n-1) = 6 * fact(5) = 6 * 120 = 720
fact(6) = 720

In the end it's the same thing as what Mike's saying, but indent-ier.

And if you turn the output on its side it's a graph of how awesome it is.

Hi David, I've been searching for a way to do exactly this! And for a factorial function, no less :)

http://stackoverflow.com/questions/21748322/how-to-print-a-recursive-trace-factorial-function

How exactly did you position your print statements to achieve that lovely return trace? The placement is eluding me...

Thanks for any help!