CODEWITHSUNDEEP
javarecursion
Tyler G
Tyler G

Reputation: 21

Reversing recursive java methods

I am reading a book called "Think Java: How to think like a Computer Scientist", and I recently covered recursive methods.

public static void countdown(int n)
{
  if (n == 0) {
      System.out.println("Blastoff!");
  } else {
      System.out.println(n);
      countdown(n - 1);
  }
}

This would be a normal recursive method used to count down to 0 and I understand what is happening, but if you make the recursive call before the System.out.println like this

public static void countdown(int n)
{
  if (n == 0) {
      System.out.println("Blastoff!");
  } else {
      countdown(n - 1);
      System.out.println(n);
  }
}

it counts the opposite way, so If I gave the argument 3 for both of these conditional statements the 1st one goes "3, 2, 1, Blastoff!" but the 2nd 1 goes "Blastoff, 1 ,2 ,3".... I don't understand how this works, can someone try to explain what is happening in this code that makes it count in the opposite way?

Upvotes: 2

Views: 1069

Answers (5)

Eric Guan
Eric Guan

Reputation: 15982

I'll try to visualize it for you.

First method

countdown(3)                (first call)
"3"                         (sysout)
    countdown(3-1)          (second call)
    "2"                     (sysout)
        countdown(2-1)      (third call)
        "1"                 (sysout)
            countdown(1-1)  (fourth call)
                "Blastoff!" (n == 0)

Second method

countdown(3)                (first call)
    countdown(3-1)          (second call)
        countdown(2-1)      (third call)
            countdown(1-1)  (fourth call)
                "Blastoff!" (n == 0. going back up call stack)
            "1"             (sysout)
        "2"                 (sysout)
    "3"                     (sysout)

Upvotes: 9

Arthur Ceccotti
Arthur Ceccotti

Reputation: 380

Think of it this way... In the first case you will always print before going down the next function, so...

countdown(3)
  System.out.println(3)
  countdown(2)
    System.out.println(2)
    countdown(1)    
      System.out.println(1)
      countdown(0)
        System.out.println("Blastoff")

Result: 3 2 1 Blastoff

In the second case, because you print it first, your run will go all the way down the recursion until the base case to start printing... 

countdown(3)
  countdown(2)
    countdown(1)
      countdown(0)
      System.out.println("Blastoff")
    System.out.println(1)
  System.out.println(2)
System.out.println(1)

Result: 1 2 3 Blastoff

Recursion is tough! I hope I helped :)

Upvotes: 4

Thilo
Thilo

Reputation: 262834

The whole point of recursion is that every step gets its own "stack frame" with its own local variables, that it remembers.

So even if you change n inside of one iteration, the function that called this iteration will still retain its own value of n. When the time comes to print this n it will still be the original value (one bigger than the one in the following iteration).

Upvotes: 0

DomGato
DomGato

Reputation: 11

The issue is that the print line is going to wait until your function call(s) have finished. Therefore it will call the function 3 times in a row before it gets to the first print line

Upvotes: 0

EntangledLoops
EntangledLoops

Reputation: 2156

It doesn't count "the opposite way", it's just that it "unravels" in an order you are perhaps not expecting. Try writing out what you expect to happen and I'll be happy to help resolve the misconception.

Upvotes: 0

Related Questions