How multiple recursion works? [closed]

I need help with a question I saw in my last exam.

Write the output of the execution of the following method by the call pX(7).

  public static void pX(int x) { 
       if (x > 1) { 
        pX(x/2);   
        pX(x/2);  
       }  
       System.out.println(x); 
    } 

I don’t understand recursion when a method calls itself twice. I tried to solve problems with multiple recursion, but I just can’t “invert” my mind in a way to multiple recursive thinking.

• Can someone explain how multiple recursion works?
• Is there any specific mechanism for understanding it?
• Will writing a recursion tree or stack call on a blank list will help to understand it?
• Is there any reading (like books or articles) about multiple recursion that’s worth reading?

Answer

Recursion is when a method or function calls itself.

Multiple Recursion is when a method or function contains multiple self-references. This is when it gets a bit tricky. Lets take a look at your example.

You call px(7), and since the parameter is over the value of 1 as your condition checks for, it will enter that code block and encounter the first recursive call, dividing your parameter by half, px(7/2), which evaluates to px(3) (rounded down for integers).

Now that you’ve entered your first recursive call, lets put your original call on hold for a sec and focus on this new call of px(3). Your condition determines that x is still greater than 1, so we encounter our first recursion within this call. So we call ourselves again, dividing the parameter by half, px(3/2) which evaluates to px(1) (again, rounded down).

Now our condition will no longer pass, so there will be no recursive calls within this iteration, We will go directly to System.out.println(x); and print out the value 1

Back to where px(3/2) got called, the next line in that condition is to do it again. So we call px(3/2) again.

Still, our condition will not pass, so we will not call any more recursive calls and go directly to System.out.println(x);

And again, back to where that second px(3/2) got called. We’ve completed our condition block and can finally call System.out.println(3);

Here are your first three lines in the output, 1,1,3

It can be kind of tricky, but you need to focus, retain and follow the call stack to really get this down.