Search code examples
javarecursiontrace

Recursion - mystery1

Having a tough time with the below code, I have answered the first call correctly as the condition is immediately correct. However, the second call of 4 is causing me great confusion, I came to the answer 2, 1 however it is incorrect- I am clearly getting things mixed up. Can someone explain to me exactly why my answer is wrong and the correct breakdown of the process of Recursive tracing in this example. I do understand elements of recursion however I am having issues following the process of tracing.

public void mystery1(int n) {
    if (n <= 1) {
        System.out.print(n);
    } else {
        mystery1(n / 2);
        System.out.print(", " + n);
    }
}

mystery1(1);
mystery1(4);
mystery1(16);
Solution

  • Recursion is beautiful yet very powerful and when it comes to observe it, people get tricked.

    Let me explain you how i learnt it when i was preparing for my GATE(Graduate Aptitude Test in Engineering).

    Think of each Function call as 2 parts:

    1. Printing
    2. Calling with halving itself

    Now all the operations will be stacked upon the older one until unless we are out of recursion and only Printing is left in the function cycle. We will print out in stack format i.e FIFO

    Example, if we have these elements in stack:

    Top: 4 3 7 2 Bottom

    It will print 4 3 7 2 .

    Now taking your Question:

    Lets break your Conditional statements in two halves, 1st will be if condition with Print 2nd will be else with its print.

    Note: Only one part i.e 1st will print 1 and that too without commas (,).

    I have attached the Image below kindly refer it, think as print statement as on stack, and the lowest print statement will be executed first as we will end out of function calls.

    enter image description here

    Now combining mystery1(1),mystery1(4),mystery1(16) the final output will be: 1 1 , 2 , 4 1 , 2 , 4 , 8 , 16

    PS: If you are going to give interviews of Amazon , Google or any Reputed Product based company they will ask question with flavor of recursion and that too without using any compiler, they wanna test your concepts via programming.