如何使用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;
    }
}


原始的响应使我感到奇怪,我认为每次索引增加时,都将使用较小的数组来调用change方法,该数组在其后开始一个索引,我猜这是正确的,但只是从概念上讲,因为这些索引仍然存在,只是无法访问。

相反,当我更改数组list1时,它也会更改数组列表,这与我期望的一样,因为它们是同一数组。就像原始帖子所暗示的那样,有没有办法“切成碎片”来制作一系列新数组,例如{4,6,8,10},{6,8,10},{8,10}等等?

最佳答案

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

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


在每个递归步骤上-将下一个索引传递给处理:


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


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

09-09 21:27
查看更多