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

Question

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

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

但是我遇到了这个答案:https://stackoverflow.com/a/5112821/10807670其中指出您应该使用原始数组，而不是“切碎”的版本，这意味着这种情况可能会意外发生。

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

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

最初的响应奇怪地让我认为每次索引增加时，都会使用一个较小的数组来调用更改方法，该数组之后开始一个索引，我猜这是正确的，但只是概念上的，因为这些索引仍然存在，只是无法访问。

相反，当我更改数组 list1 时，它也会更改数组列表，正如我所料，因为它们是相同的数组。有没有办法像原始帖子所暗示的那样“将其切碎”，例如制作一系列新数组，例如 {4,6,8,10}、{6,8,10}、{8,10}等等？

Answer 1

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

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

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

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 个步骤

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