CODEWITHSUNDEEP
javarecursion
StaticStacksStack
StaticStacksStack

Reputation: 71

Having trouble tracing recursive method in Java

This is a rather quick question. I have been having trouble understanding the concept of recursion in Java and I was wondering if someone could help me. I have been tracing successfully 5 out of the 6 recursive methods that I have done, but this one is throwing me for a loop, literally. I was expecting the output to be just 2(the output I traced), but when I put it into my compiler it came out with 1213121(proper output). As I said, I have been able to do this thus far, but this one is confusing me. Here is what I am working with:

public class Recursion
{
    public static void main(String [] args)
    {
        Recursion r = new Recursion();
        r.doSomething(3);
    }

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

Upvotes: 2

Views: 659

Answers (3)

asad_hussain
asad_hussain

Reputation: 2001

Here is the diagramatic representation of how the control flows through this recursion program.

I think the diagram should clear your doubts.

enter image description here

Upvotes: 3

Aman Goyal
Aman Goyal

Reputation: 393

Let's give line numbers to below code to ease further explanation.

  1. doSomething(n-1);

  2. System.out.print(n);

  3. doSomething(n-1);

    line 1 redirect call until you reach at n=1. In the end line will call doSomething(0). because n>0, it will return and will print 1. Then again line 3 will call doSomething(0) and will return to previous caller which was n=2. It will print 2 and will call doSomething(1). Which will print 1 (121) and will return to n=2,line3. From here it will return to previous caller where n=3. Line 2 will print 3(1213). Then line 3 will call doSomething(2) which will append 121 as previous call which will ultimately become 1213121.

I hope this helps.

Upvotes: 0

David Choweller
David Choweller

Reputation: 1050

I would prefer to do this in the comments, but the formatting of the comments make it hard to follow. You can follow this recursion as if it were a math equation.

The basic logic is:

DoSomething(n) results in:

  • doSomething(n-1)
  • print n
  • doSomething(n-1)

So let's follow this for doSomething(3)

  • doSomething(2)
  • print 3
  • soSomething(2)

So now we have to figure out what doSomething(2) does, so just plug in the values with n=2:

  • doSomething(1)
  • print 2
  • doSomething(1)

Now plug in the values for n=1:

  • doSomething(0)
  • print 1
  • doSomething(0)

doSomething(0) is the base case, where the recursion stops. Basically doSomething(0) does nothing.

Therefore, the actions for n=1 become

  • print 1

Therefore, the actions for n=2 become

  • print 1
  • print 2
  • print 1

Therefore, the actions for n=3 become

  • print 1
  • print 2
  • print 1
  • print 3
  • print 1
  • print 2
  • print 1

Upvotes: 4

Related Questions