2

So, what the question asks is what will the output of this method be when you pass it a 3.

I plugged it into JCreator and got 010203010 and I am utterly confused how.

public static void printX(int n){
    if (n<= 0)
        System.out.print(0);
    else{
        printX(n-1);
        System.out.print(n);
        printX(n-2);
    }
}

So my logic with this is, So it will call 3-1 which will call 2-1 which will call 1-1 which will print out a zero, print out a one, and then print out another zero because 1-2 is less than 0.

So we have 010 so far on this first "plug in" on the recursive way back up.

So here is where it confuses me, it doesn't really return anything, it just prints, so calling printX(2-1) now, where the hell does it get its value? All I can think it will do is call itself again and again and just calling it self one less time, and reaching the base case like 4 or 5 different times.

Improve this question
5
  • 3
    Walk through the logical steps, each one, on paper, and you'll see. Pretend that YOU are the JVM, and run your program in your head. Commented Apr 21, 2014 at 23:54
  • 1
    In particular, you need to model, on paper, the call stack. You will have up to four calls to PrintX running at the same time, and you need to remember the parameter for each of them. Commented Apr 21, 2014 at 23:57
  • I tried that, but whenever I get to printX(2-1) on the second step, I have no clue where to go from there. Commented Apr 21, 2014 at 23:57
  • 4
    Sometimes it's better to start simpler. Try running through the program with an input of 1, and then when you're done with that, try 2. Commented Apr 22, 2014 at 0:00
  • 1
    When it resumes from the recursions that printx(n-1) outputs it prints out n and then it repeats the same recursion of print(n-1). It does this in EVERY instance except the ones that hit the base case of n <= 0 where it just prints 0. It's pretty much like if you had 3 System.out.println("Im Here"); in code you'd expect the two last to execute after the first had finished. Commented Apr 22, 2014 at 0:08

5 Answers 5

Reset to default
1

Ok, here is the logic:

PrintX(3) -> PrintX(3 - 1)

PrintX(2) -> PrintX(2 - 1)

PrintX(1) -> PrintX(1 - 1) which prints the first 0.

Then PrintX(1) prints the 1 and calls PrintX(1 - 2) which prints the second 0.

Then PrintX(2) prints the 2 and calls PrintX(2 - 2) which prints the third 0.

Then PrintX(3) prints the 3 and calls PrintX(3 - 2)

PrintX(1) -> PrintX(1 - 1) which the prints the fourth 0.

Then PrintX(1) prints the 1 and calls PrintX(1 - 2) which prints the last 0.

This all prints: 010203010

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

I don't understand why it doesn't call print (2-1) in the second call then! Because it seems as if you are omitting it from the Print(2) call but the Print (1) call used it to get the first zero.
1

There is a call stack in the system where method calls are stored as you call them. (Stack wiki)

  • As the currently executing method is in the stack, when it calls another method, the new method is added (pushed) on top of the stack and current method is paused (not in exact terminology).
  • When the method at top (latest call) finishes it's execution, it is popped from the stack and the previous method resumes it's execution.

Along with method name, method parameter(s) and other required states are also stored to the stack.

Now considering this logic, you can easily reproduce stack states and order in which method calls will happen on a paper.

This way you can see which numbers should be printed (which would be 010203010).

Hope this helps.
Good luck.

Improve this answer

Comments

1

One way to answer a question like this, without stepping through and keeping track of the call stack, is to notice, from looking at the code, that printX(n) prints

  1. "0" if n <= 0;
  2. the result of printX(n-1) + n + the result of printX(n-2) otherwise.

Using the above, you can figure out that printX(1) prints "010", by using rule 2. You can write that result down. Now, figure out what printX(2) will print, using rule 2 and using the result you've already written down, and write that down; then figure out what printX(3) will print, using rule 2 and using the other results you've written down.

Improve this answer

1 Comment

That's by far the best method to "get" it. It also teaches an important lesson in abstraction: You figure out what printX (0) does. Then you figure out what printX (1) does. Then you figure out what printX (2) does, and you don't care about the details of printX (0) and printX (1): You know what they day, there's no need anymore to care how they do it. So at each step, the problem is simple.
0

Here's the first half:

call printX with 3
printX(3): n>0 so call printX with 2
   printX(2): n>0 so call printX with 1
      printX(1): n>0 so call printX with 0
          printX(0): n==0, print out "0" and return
      printX(1): we're back.  print out n, which is "1"
      printX(1): call printX with -1
          printX(-1): n<0, print out "0" and return
      printX(1): we're back.  return
   printX(2): we're back.  print out n, which is "2"
   printX(2): call printX with 0 
...
Improve this answer

Comments

0

Let's follow the tree of recursive calls. First, what each call with each distinct number does:

printX(3) => printX(2), then "3", then printX(1)
printX(2) => printX(1), then "2", then printX(0)
printX(1) => printX(0), then "1", then printX(-1)
printX(0) => "0"
printX(-1) => "0"

Then putting it all together.

printX(3) => printX(2), then "3", then printX(1) =>
(printX(1), then "2", then printX(0)), then "3", then (printX(0), then "1", then
    printX(-1)) => 
((printX(0), then "1", then printX(-1)), then "2", then "0"), then "3", (then "0",
    then "1", then "0") => 
//  <------------- from printX(2) ------------>
//  <-- from printX(1) --->                                <--- from printX(1) ---
    "0", then "1", then "0", then "2", then "0", then "3", then "0", then "1",
// ------------>
        then "0" =>
"010203010"
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.