CODEWITHSUNDEEP
javarecursion
user3564040
user3564040

Reputation:

Double recursion - Java

i've got a problem. I can't understand how to think when I get this code:

public class MysteryClass {
   public static void mystery(int n) {
      if (n > 0){
         mystery(n-1);
         System.out.print(n * 4);
         mystery(n-1);
      }
   }

   public static void main(String[] args) {
      MysteryClass.mystery(3);
   }
}

The answer is 4 8 4 12 4 8 4 but i don't know how they got it.. could someone please explaine ?

Upvotes: 1

Views: 943

Answers (6)

monocell
monocell

Reputation: 1441

The trick to understand recursion is to think about different cases imo, not to mentally trace the call graph.

Your mystery function deals with two different cases:

  • n =< 0 : Do nothing

  • n > 0 :

    • do something recursive to with n decremented, don't care what.
    • print n * 4
    • do the recursive thing again.

We can see that the only thing this function can do is print some numbers. So for n == 3 we get (Maybe print stuff) 12 (Maybe print stuff)

Now, lets replace the unknown stuff with with the the same call for n == 2 and we get

((Maybe print stuff) 8 (Maybe print stuff)) 12 ((Maybe print stuff) 8 (Maybe print stuff))

If we can keep the base case in mind, i.e. that mystery does nothing when n == 0 I think the structure of the call is most apparent when it's not expanded multiple times. You can keep substituting to make sure your answer is correct, but when trying to figure out what a recursive function does it generally just hurt my brain to try to think to deeply about exactly what calls are made.

Upvotes: 0

Raul Guiu
Raul Guiu

Reputation: 2404

You can modify the class to print the order of the calls:

public class MysteryClass {
  static int COUNTER = 0;
  public static void mystery(int n) {
    int callOrder = COUNTER;
    COUNTER++;
     if (n > 0){
        mystery(n-1);
        System.out.println(n * 4 +"  (order: "+callOrder+", n: "+n+")");
        mystery(n-1);
     } else {
       System.out.println("wont print and wont recurse(negative): " +"(order: "+callOrder+", n: "+n+")");
     }
  }

  public static void main(String[] args) {
     MysteryClass.mystery(3);
  }
}

This prints:

wont print and wont recurse(negative): (order: 3, n: 0)
4  (order: 2, n: 1)
wont print and wont recurse(negative): (order: 4, n: 0)
8  (order: 1, n: 2)
wont print and wont recurse(negative): (order: 6, n: 0)
4  (order: 5, n: 1)
wont print and wont recurse(negative): (order: 7, n: 0)
12  (order: 0, n: 3)
wont print and wont recurse(negative): (order: 10, n: 0)
4  (order: 9, n: 1)
wont print and wont recurse(negative): (order: 11, n: 0)
8  (order: 8, n: 2)
wont print and wont recurse(negative): (order: 13, n: 0)
4  (order: 12, n: 1)
wont print and wont recurse(negative): (order: 14, n: 0)

You can verify that what @bgamlath said in his answer match what happens. order refers to the order in which the calls to the recursive method are made.

You can also see symetry, the call with order 0, printing 12 in the middle and the same results from the recursion 4, 8, 4 (symetric too) above and bellow. If you start with 4 you will see a bigger example of that symmetry due the recursion before and after.

Upvotes: 0

Ambroos
Ambroos

Reputation: 3476

It's quite simple!

This is what happens:

mystery(n = 3):
    mystery(n = 2):
        mystery(n = 1):
            mystery(n = 0):
                n > 0 = false
            << done with mystery(n = 0)
            PRINT n * 4 = 4
            mystery(n = 0):
                n > 0 = false, this doesn't print anything
                << done with mystery(n = 0)
            << done with mystery(n = 1)
        PRINT n * 4 = 8 
        mystery(n = 1):
            mystery(n = 0):
                n > 0 = false, this doesn't print anything
                << done with mystery(n = 0)
            PRINT n * 4 = 4
            mystery(n = 0):
                n > 0 = false, this doesn't print anything
                << done with mystery(n = 0)
            << done with mystery(n = 1)
        << done with mystery(n = 2)
    PRINT n * 4 = 12
    mystery(n = 2):
        mystery(n = 1):
            mystery(n = 0):
                n > 0 = false, this doesn't print anything
                << done with mystery(n = 0)
            PRINT n * 4 = 4
            mystery(n = 0):
                n > 0 = false, this doesn't print anything
                << done with mystery(n = 0)
            << done with mystery(n = 1)
        PRINT n * 4 = 8 
        mystery(n = 1):
            mystery(n = 0):
                n > 0 = false, this doesn't print anything
                << done with mystery(n = 0)
            PRINT n * 4 = 4
            mystery(n = 0):
                n > 0 = false, this doesn't print anything
                << done with mystery(n = 0)
            << done with mystery(n = 1)
        << done with mystery(n = 2)
    << done with mystery(n = 3)

Upvotes: 0

Joe
Joe

Reputation: 1535

Think about the first few calls and the pattern is apparent;

n = 3
mystery(n-1); ->

   // recursive call
   n = 2 
   mystery(n-1); ->

      // recursive call
      n = 1
      mystery(n-1); ->

         // inside recursion      
         n = 0 // Do nothing

      System.out.print(n * 4);  // = 4
      mystery(n-1);

         // inside recursion
         n = 0 // Do nothing

   System.out.print(n * 4);  // = 8
   mystery(n-1); ->

      // inside recursion
      n = 1
      mystery(n-1); ->

         // inside recursion
         n = 0 // Do nothing

      System.out.print(n * 4);  // = 4
      mystery(n-1);

         // inside recursion
         n = 0 // Do nothing

... You get the idea

Upvotes: 0

Dropout
Dropout

Reputation: 13866

In the mystery(int n) method you call itself twice with

mystery(n-1);

In between the recursive calls you output the value of the original call multiplied by four.

This means that even before the first output, you call the method again with n-1, and in the call you call it again with n-1. The first number is the second iteration of the first call. The second number is the first iteration and so on. It's kind of hard to explain with just words. You might be more successful in understanding it by debugging step-by-step.

Upvotes: 0

Buddhima Gamlath
Buddhima Gamlath

Reputation: 2328

This is how the function calls are made. To understand more, get a pencil and a paper and draw what happens. First, do it for mystery(1). Then continue with mystery(2) and mystery(3)

mystery(3)
    msytery(2)
        mystery(1)
            mystery(0)
            prints 1 * 4
            mystery(0)
        prints 2 * 4
        mystery(1)
            mystery(0)
            prints 1 * 4
            mystery(0)
    prints 3 * 4
    msytery(2)
        mystery(1)
            mystery(0)
            prints 1 * 4
            mystery(0)
        prints 2 * 4
        mystery(1)
            mystery(0)
            prints 1 * 4
            mystery(0)

Upvotes: 7

Related Questions