Java 递归 - 数组中整数的倒序，它是如何工作的？

Question

  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

一切都非常简单，有一个名为 reversePrint 的函数。当您将这些数字传递给函数 reversePrint 时，它会取出第一个值（在本例中为“5”），然后再次调用 reversePrint，现在使用较小的列表。

这一直持续到最后我们没有更多的数字，并开始打印出来。

我的困惑是在'10'行，如果每次删除第一个号码，号码列表越来越少，调用'System.out.println(numbers[0]);'如何检索已从列表中删除的号码，并以相反的顺序这样做？

Answer 1

的实施非常低效

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

但为了回答您的问题，reversePrint 创建了一个新数组，其中第一项从数组中删除，然后打印出原始数组的第一项。第二个调用将收到 [1, 34, 12, 7] 因为第一个调用已经删除了 5，所以它会打印出 1.

Answer 2

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

在此代码中没有从任何数组中删除任何数字。每个递归调用都会创建一个新数组并将当前数组中除第一个元素之外的所有元素复制到其中。

因此传递给第 i 次调用 reversePrint() 的数组包含原始数组的最后 n-i+1 个元素。

当为空数组调用reversePrint()时，递归结束。当最后一次递归调用 returns 时，倒数第二个调用打印 numbers[0]，其中包含原始数组的最后一个元素。然后前面的reversePrint()打印出numbers[0]，其中包含原数组的倒数第二个元素，依此类推...

这些是递归调用：

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

现在，在每个 returns 之后打印 numbers[0]，所以你得到

Answer 3

这里有一个方案来理解这个递归中的调用栈：

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);
};

如您所见，System.out.println(numbers[0]) 在传播递归后被调用。请注意，每次调用都会创建一个新数组，您不会丢失第一个数字。

Answer 4

首先，您实际上并没有删除数字：您将它们从 numbers 复制到 a，跳过位置 0 的数字。 System.out.println 从 numbers 打印，因此索引 0 处的整数仍然相同。

其次，System.out.println语句在递归调用之后，所以它将在returns调用之后执行。所以基本上，将执行的第一个 System.out.println 将是最后一次调用中的那个：

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

Answer 5

也许以经典方式进行操作（而不是像您那样复制数组）会更清楚发生了什么。

// 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);
}

Java 递归 - 数组中整数的倒序，它是如何工作的？

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

java

arrays

int

recursion

reverse