CODEWITHSUNDEEP
javaarraysrecursionintreverse
Tamim Saiyed
Tamim Saiyed

Reputation: 3

Java Recursion - reverse order integers from an array, how it works?

  public static void reversePrint(int[] numbers){
     if(numbers.length == 0) //Base case
         return;  

     int[] a = new int[numbers.length-1];
     for(int i = 0; i < numbers.length-1;i++)
         a[i] = numbers[i+1];

     reversePrint(a);
     System.out.println(numbers[0]); 
  }

 public static void main(String[] args){

   int[] array = new int[]{5,1,34,12,7};
     reversePrint(array);
}


Output:
 7
 12
 34
 1
 5

Everything is pretty straightforward, have a function called reversePrint. When you pass those numbers to the function reversePrint, it takes the first value out, (in this case '5') and then it calls reversePrint again,now with the smaller list.

This Continues until finally we're left with no more numbers, and begins to print them out.

My confusion is in line '10', if the list of numbers is getting less and less by removing the first number each time, how does calling 'System.out.println(numbers[0]);' retrieve numbers that have been removed from the list, and doing so in reverse order?

Upvotes: 0

Views: 94

Answers (5)

Oneiros
Oneiros

Reputation: 4378

Here's a scheme to understand the stack of calls in this recursion:

reversePrint([5,1,34,12,7]) {
   reversePrint([1,34,12,7]) { // <-- this list IS A COPY, it just ignores the first number
      reversePrint([34,12,7]) {
         reversePrint([12,7]) {
            reversePrint([7]) {
               reversePrint([]);
               print(7); // <-- this is the first number of the current list
            };
            print(12);
         };
         print(34);
      };
      print(1);
   };
   print(5);
};

As you can see, the System.out.println(numbers[0]) is called AFTER propagating the recursion. Note that a new array is created in each call, you don't lose the first number.

Upvotes: 2

OldCurmudgeon
OldCurmudgeon

Reputation: 65821

Perhaps doing it the classic way (rather than making a copy of the array as you do) it would be clearer what is happening.

// Private version to pass the offset which increases on each call.
private static void reversePrint(int[] numbers, int from){
    // Base case - stop at end of array.
    if(numbers.length > from) {
        // Print everything else first.
        reversePrint(numbers, from+1);
        // Then the one I am at.
        System.out.println(numbers[from]);
    }
}

public static void reversePrint(int[] numbers){
    reversePrint(numbers, 0);
}

public void test() throws Exception {
    System.out.println("Hello world!");
    int[] array = new int[]{5,1,34,12,7};
    reversePrint(array);
}

Upvotes: 0

Luca Negrini
Luca Negrini

Reputation: 490

First, you don't actually remove numbers: you copy them from numbers to a skipping the one in position 0. That System.out.println prints from numbers, so the integer at index 0 will still be the same.

Second, the System.out.println statement is after the recursive call, so it will be executed after that call returns. So basically, the first System.out.println that will execute will be the one in the last call:

for ...
reversePrint
|
|    for ...
|    reversePrint
|    |
|    |    for ...
|    |    reversePrint
|    |    |
|    |    |    for ...
|    |    |    reversePrint
|    |    |    |
|    |    |    |    for ...
|    |    |    |    reversePrint
|    |    |    |    |
|    |    |    |    |    return
|    |    |    |    |
|    |    |    |    System.out.println
|    |    |    |
|    |    |    System.out.println
|    |    |
|    |    System.out.println
|    |
|    System.out.println
|
System.out.println

Upvotes: 1

Eran
Eran

Reputation: 393846

how does calling 'System.out.println(numbers[0]);' retrieve numbers that have been removed from the list, and doing so in reverse order?

No numbers have been removed from any array in this code. Each recursive call creates a new array and copies to it all the elements of the current array except of the first element.

Therefore the array passed to the i'th call to reversePrint() contains the last n-i+1 elements of the original array.

The recursion ends when reversePrint() is called for an empty array. When the last recursive call returns, the next to last call prints numbers[0], which contains the last element of the original array. Then the previous reversePrint() prints numbers[0], which contains the next to last element of the original array, and so on...

These are the recursive calls:

reversePrint({5,1,34,12,7})
reversePrint({1,34,12,7})
reversePrint({34,12,7})
reversePrint({12,7})
reversePrint({7})
reversePrint({})

Now, after each of them returns, numbers[0] is printed, so you get 

7
12
34
1
5

Upvotes: 0

daniu
daniu

Reputation: 15008

That's an exceptionally ineffective implementation of

Arrays.asList(5, 1, 34, 12, 7).reverse().forEach(System.out::println)

But to answer your question, the reversePrint creates a new array with the first item removed from the array, then prints out the first of the original. The second call will receive [1, 34, 12, 7] because the first has removed the 5, so it will print out the 1.

Upvotes: 0

Related Questions