如何使用递归来处理 "chopping up" 数组？

Question

如何在 Java 中使用递归从主数组创建新的、更小的数组？我能想到的唯一方法就是return一个数组，否则会超出范围。

我来这里的目的是寻找证据来证明通过数组递归与循环一样有效，因为方法中定义的数组和本地数组都指向内存中的相同位置。

但是我遇到了这个答案：指出你应该使用原始数组，而不是 "chopped-up" 版本，这意味着这样的事情可能会偶然发生。

我设法证明了主数组和方法中定义的数组是同一个数组，但我仍然不确定如何使用递归从原始数组创建多个子数组。

class Main {
  public static void main(String[] args) {
    int[] list={2,4,6,8,10};
    System.out.println(list[0]);
    System.out.println(list[1]);
    change(list, 0);
    System.out.println(list[0]);
    System.out.println(list[1]);
  }

  public static void change(int[] list1, int index){
      //does a recursive call initialize a new array or does it point to the same array in memory?

    list1[index]=1; //set all indices to 1

    if (index==list1.length-1) return;

    else change(list1, index+1);
    return;
    }
}

奇怪的是，最初的回复让我认为每次递增索引时，都会用一个较小的数组调用 change 方法，该数组在其后开始一个索引，我猜这是真的，但只是概念上的，因为那些索引仍然存在, 只是没有被访问。

相反，当我更改数组 list1 时，它也会更改数组列表，正如我预期的那样，因为它们是同一个数组。有什么方法可以 "chop it up" 正如原来的 post 所暗示的那样，让我们说，制作一系列新数组，如 {4,6,8,10}, {6,8,10}, { 8,10}等？

Answer 1

要以递归方法创建新的子列表，请创建数组范围的副本。看看https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#copyOfRange(int[],%20int,%20int)

Answer 2

java 中所有非原始值的传递都是通过引用完成的，因此它是递归调用中的同一个数组，正如您已经证明的那样。但是循环仍然更有效一些，因为调用函数需要额外的操作（例如，复制函数的参数）。循环不需要这些动作，所以我想说它在效率方面仍然胜出。以下是对 Java 中调用方法时发生的情况的解释：What happens after a method is called in Java

Answer 3

递归处理数组可以用不同的形式实现。为了实用，我将比较两种常见的内存使用方式。

假设我们要求数组元素的总和。让我们考虑两种方式：

在每个递归步骤中 - 将下一个索引传递给进程：

int sum(int[] nums) {
  return sum(0, nums);
}

int sum(int index, int[] nums) {
  if (index == nums.length) {
    return 0;
  } else {
    return nums[index] + sum(index + 1, nums);
  }
}

在每个递归步骤中 - 将新数组传递给进程：

int sum(int[] nums) {
  if (nums.length == 0) {
    return 0;
  } else {
    return nums[0] + sum(Arrays.copyOfRange(nums, 1, nums.length));
  }
}

这两种方式都会找到数组元素的总和。但它会带来不同的成本：

第一种方法将使用 O(n) 额外内存，因为在每个递归步骤中，它只需要分配常量 O(1) 内存量，并且总共有 n步骤
第二种方法将使用 O(n^2) 额外的内存，因为在每个递归步骤中它需要分配 O(n) 额外的内存（当创建原始数组的副本时）并且总体而言是 n 步

在实践中，您会发现不同的变化，老实说，哪种方法最好，实际上取决于手头的任务。

如何使用递归来处理 "chopping up" 数组？

How would one go about "chopping up" an array using recursion?

java

arrays

recursion

sublist