CODEWITHSUNDEEP
javarecursion
synshreds
synshreds

Reputation: 13

Can someone walk me through the Java recursion process for this code?

I am having a bit of trouble understanding the process of recursion for this specific code.

public static void testMethod(int n){

      if(n > 0){
         testMethod(n-1);
         System.out.print("A");
         testMethod(n-1);
         System.out.print("B");
      }
}

For example, if in my main method I type

testMethod(2);

The output for the code is: ABAABB.

In my head I am thinking this code would run until n=0 making it skip the if statement, but run a total of 3 times and output AB each time. Clearly, I am not thinking of this correctly.

If anyone could walk me through the process of why this is ABAABB and not something like ABABAB I would greatly appreciate it!

Upvotes: 1

Views: 111

Answers (7)

User_67128
User_67128

Reputation: 1250

If you are familiar with tree structure and its traversal then it is much easier to understand the working process of any recursion method. For this method the recursion tree will be something like this:

enter image description here

For n=2, the complete tree will be the following:

enter image description here

Now you need to traverse the tree fro left to right (inorder-based, only leaves), you will get:

print ("A") print ("B") print ("A") print ("A") print ("B") print ("B")

which is : ABAABB

Upvotes: 1

RaceYouAnytime
RaceYouAnytime

Reputation: 734

You can actually step through this visualizing what n will be each step along the way.

Probably the most important point is that when the recursion gets to 1-case, it prints "AB," but even when it is not in its 1-case, it will print an A after calling itself the first time and B after calling itself the second time. So when we call for 2, we expect a 1-case ("AB"), then an "A" and then a 1-case ("AB"), and then a "B". Or "ABAABB"

testMethod(2) {
--testMethod(1) {
----testMethod(0);
----System.out.print("A");
----testMethod(0);
----System.out.print("B");
--}
--System.out.print("A");
--testMethod(1) {
----testMethod(0);
----System.out.print("A");
----testMethod(0);
----System.out.print("B");
--}
-- System.out.print("B");
}

If you walk through the prints in order, it makes sense that you would get this output.

Upvotes: 2

steffen
steffen

Reputation: 16968

So let's say your code lines are

public static void testMethod(int n) {
    if (n > 0) {
        testMethod(n - 1);       /* line1 */
        System.out.print("A");   /* line2 */
        testMethod(n - 1);       /* line3 */
        System.out.print("B");   /* line4 */
    }                            /* line5 */
}

Then you'd have these steps:

 1. n=2: line1 -> testMethod(n=1)
 2. n=1: line1 -> testMethod(n=0)
 3. n=0: line5 -> return
 4. n=1: line2 -> prints "A"
 5. n=1: line3 -> testMethod(n=0) 
 6. n=0: line5 -> return
 7. n=1: line4 -> prints "B"
 8. n=1: line5 -> return
 9. n=2: line2 -> prints "A"
10. n=2: line3 -> testMethod(n=1)
11. n=1: see 2-8
... n=1:          prints "AB"
18. n=2: line4 -> prints "B"
19. n=2: line5 -> return

Upvotes: 1

Abs
Abs

Reputation: 300

The key is to remenber that, once a recursion is called, all the instructions in that sub call are executed before the remaining instructions in the parent get executed. And there're two recursion calls to (n-1) in your code, one before each print.

Let's try to visualize the call stack for testMethod(2) : n=2 > 0, then main stack is :

1. testMethod(1); // 2- 1
2. System.out.print("A");
3. testMethod(1); // 2 - 1
4. System.out.print("B");`

Now let's consider the subcall testMethod(1) n=1 > 0, stack for testMethod(1); => 

testMethod(0); // 1-1
System.out.print("A");
testMethod(0); // 1 -1
System.out.print("B");`

Since testMethod(0); doesn't do anything ( 0 is not > 0) we can remove testMethod(0) to simplify the stack for testMethod(1); => 

System.out.print("A");
System.out.print("B");`

Now let's replace that back in the main stack for testMethod(2) =>

1.1 System.out.print("A");//-----
                                 //-----> testMethod(1)
1.2 System.out.print("B");`//----

2. System.out.print("A");

3.1 System.out.print("A");//-----
                                 //-----> second testMethod(1)
3.2 System.out.print("B");`//----

4. System.out.print("B");`

Which then prints out in order ABAABB

Cheers!

Upvotes: 1

Mohammed Housseyn Taleb
Mohammed Housseyn Taleb

Reputation: 1828

in Java we have a stack that stores all our calls with the values

in your first call your program will hold a stack reference to your first call with value 2 so we can say

public static void testMethod(2){

      if(2 > 0){
Label A: testMethod(1); ==> this will trigger a call and our stack will refer to this line to coninue when the method ends
         System.out.print("A");
         testMethod(1);
         System.out.print("B");
      }
}

our Label A will look like the following and you have to know that we have no printing till now

public static void testMethod(1){

      if(1 > 0){
Label B: testMethod(0); ==> in this case we have a new method call, new stack reference and we wait for this method return so we continue to next line
         System.out.print("A");
         testMethod(0);
         System.out.print("B");
      }
}

if we try to look at the stack with our eyes we will see that

testMethod(2) wait in Label A ==> call TestMethod(1) wait in Label B call testMehod(0)

you know that 0 is not greater than 0 so you will terminate without processing

this will free the label B to jump to next line where it will print A then call with 0 value wich will do nothing then print B

here is our first AB

now it will return to label A and jump to next line and print A

we have ABA we will recall another time the testMethod1 we know that this road has printed AB so we will have

ABA+AB = ABAAB then the call terminate and finish by priting B and exit the call of testMethod(2)

with printing ABAABB

Upvotes: 0

cybersam
cybersam

Reputation: 66999

For the sake of illustration, let's pretend that testMethod(n-1) prints "-". Then testMethod(n) will print out "-A-B".

Upvotes: 1

ln_x
ln_x

Reputation: 11

So first testMethod ist called with 2. Its checking if 2 > 0 -> true

Now lets say to make it more clear testMethod1 is called with 1 Its checking if 1 > 0 -> true

Now testMethod2 is called with 0.

0 > 0 -> false this call does nothing so back to testMethod1

testMethod1 prints A calls testMethod3 with 0 so nothing happens again and back to testMethod1 again testMethod1 print B and now we're going back to the original testMethod call

A is printed and now we're doing the same stuff again so AB is printed and finally B

Upvotes: 1

Related Questions