我需要帮助来理解这个使用递归找到数组最小值的算法是如何工作的
I need help understanding how this algorithm that finds smallest value of an array using recursion works
我目前正在学习数据结构并正在学习递归。下面发布的 code/algorithm 应该使用递归找到数组的最小值。但是，我无法理解它是如何工作的。我的老师的解释不是很有帮助，所以如果有人知道如何很好地解释这一点，我将不胜感激！
public class Recursive {
public static int minimum(int array[], int first, int last) {
int answer;
int mid;
int minFirst;
int minSecond;
if(first == last)
return array[first];
else {
mid = (first + last) / 2;
minFirst = minimum(array, first, mid);
minSecond = minimum(array, mid + 1, last);
}
if(minFirst < minSecond)
answer = minFirst;
else
answer = minSecond;
return answer;
}
}
为了更好地理解代码的工作原理，让我们放一些打印语句。这将告诉我们该方法的每次递归正在处理哪些数据。
我在代码中添加了一些注释。
public class Test {
public static void main(String[] args) throws Exception {
int[] arr = {4,3,2,1};
System.out.println("\nThe smallest element is : " +minimum(arr, 0, 3, 1));
}
//this method finds smallest element within given range in an array
public static int minimum(int array[], int first, int last, int indent) {
//lets print what each recursion is working on
int[] subArray = Arrays.copyOfRange(array, first, last+1);
System.out.println(" ".repeat(indent) + "Invoked with: first="
+ first + " last=" + last
+ " Array=" + Arrays.toString(subArray));
int answer;
int mid;
int minFirst;
int minSecond;
if(first == last) {
System.out.println(" ".repeat(indent) + "Selected " + array[first]);
return array[first];
}
else {
//divide the range in half
mid = (first + last) / 2;
//find smallest element from first half
minFirst = minimum(array, first, mid , indent + 3);
//find smallest element from second half
minSecond = minimum(array, mid + 1, last, indent +3);
}
//select smallest element from both halves
if(minFirst < minSecond)
answer = minFirst;
else
answer = minSecond;
System.out.println(" ".repeat(indent) + "Selected " + answer + " from " + minFirst + ", " + minSecond);
return answer;
}
}
输出：
Invoked with: first=0 last=3 Array=[4, 3, 2, 1]
Invoked with: first=0 last=1 Array=[4, 3]
Invoked with: first=0 last=0 Array=[4]
Selected 4
Invoked with: first=1 last=1 Array=[3]
Selected 3
Selected 3 from 4, 3
Invoked with: first=2 last=3 Array=[2, 1]
Invoked with: first=2 last=2 Array=[2]
Selected 2
Invoked with: first=3 last=3 Array=[1]
Selected 1
Selected 1 from 2, 1
Selected 1 from 3, 1
The smallest element is : 1
您也可以像 Eclipse 一样使用 IDE 的 debug feature。
该方法在 first 和last 指定的范围内查找数组中的最小元素。所以 minimum(arr, 4, 6) 会在 arr[4]、arr[5] 和 arr[6] 中找到最小值。
让我们看看它是如何做到的。
如果first与last相同，指定范围内只有一个元素，即array[first]（或array[last]，即一样）。最小的元素一定是那个元素，所以 return array[first].
否则，我们要将范围分成两半。为此，我们首先通过 (first + last) / 2 找到范围的中点 - 计算 first 和 last 的平均值。那么两半是：
- 从
first 到 mid
- 从
mid + 1 到 last
然后我们找到每一半中的最小元素，因此：
minimum(array, first, mid)minimum(array, mid + 1, last)
我知道在我们还没有完成声明它的作用时如何使用 minimum 方法是违反直觉的，但是让我们相信自己 minimum 会做它应该做的- 找到最后两个参数指定的范围之间的最小值。
然后我们比较这些最小值。这些最小值中的较小者是整个范围内的最小元素（最后一个 if 语句在做什么）。
几乎每个递归算法都包含两个关键部分：
琐碎的案例
所有递归算法都会为微不足道的输入提供瞬时答案（并且不会递归）。
在这种特定情况下，简单的输入情况是当 'first' 和 'last' 彼此相等时：该方法的目的是 return 在其中找到的最小值从索引 'first' 开始到索引 'last' 结束的所有值。当 first 和 last 相等时，只有一个数字可供查看。那么，'what is the smallest number amongst this giant collection of.... 1 number' 就是……那个数字。那是微不足道的情况。
小案例的进展。
所有其他情况都通过首先再次调用您自己的方法来解决，但是使用修改后的输入 - 应该修改输入，以便它们以某种方式更接近边缘情况。有时，你多次调用自己的方法，但是 all 这样的调用必须保证 all 更接近普通情况，然后你组合单独的答案。
在这种情况下，问题表述为：
要从数字列表中找到最小的数字，首先，将数字列表分成大致相等的两部分。这些列表更小，因此也更简单，所以我们可以要求自己计算这些较小列表的答案 - 没关系，我们将它们移到了平凡的情况下，我们可以做到。然后，将获得的两个答案组合起来：只 return 最小的答案，将较大的答案分块。
就是这样。
这就是编写递归代码所需的全部内容。如果您从这些方面考虑它是有道理的：对于任何输入，该算法都是根据应用于计算稍微简单问题的结果的简单操作来重述问题。
那个稍微简单一点的问题的结果是用同样的方式完成的：通过对一个更简单的问题的计算结果应用一个简单的操作。
冲洗并重复直到问题非常简单，答案显而易见并且可以立即提供。
再补上log，大家可以看清楚了：
import java.util.Arrays;
import java.util.concurrent.atomic.AtomicInteger;
public class Recursive {
private static AtomicInteger step = new AtomicInteger();
public static int minimum(int array[], int first, int last) {
int answer;
int mid;
int minFirst;
int minSecond;
int currentStep = step.incrementAndGet();
System.out.println("=================== step: " + currentStep + "=============");
int[] currentArray = new int[last - first];
System.arraycopy(array, first, currentArray, 0, currentArray.length);
System.out.println("current array(" + first + ", " + last + "): " + Arrays.toString(currentArray));
System.out.print(String.format("first(%d) == last(%d): %b", first, last, first == last));
if(first == last) {
System.out.println(", so min = " + array[first]);
return array[first];
}
else {
System.out.println(", so divide 2 the array");
mid = (first + last) / 2;
minFirst = minimum(array, first, mid);
int minFirstStep = step.get();
minSecond = minimum(array, mid + 1, last);
int minSecondStep = step.get();
System.out.print(String.format("compare min of step[%d] and step[%d]: %d < %d = %b",
minFirstStep,
minSecondStep,
minFirst,
minSecond,
minFirst < minSecond));
}
if(minFirst < minSecond)
answer = minFirst;
else
answer = minSecond;
System.out.println(", so min = " + answer);
return answer;
}
public static void main(String[] args) {
int array[] = {1, 4, 7, 8, 5, 2};
int min = minimum(array, 0, array.length - 1);
System.out.println("min is: " + min);
}
}
输出：
=================== step: 1=============
current array(0, 5): [1, 4, 7, 8, 5]
first(0) == last(5): false, so divide 2 the array
=================== step: 2=============
current array(0, 2): [1, 4]
first(0) == last(2): false, so divide 2 the array
=================== step: 3=============
current array(0, 1): [1]
first(0) == last(1): false, so divide 2 the array
=================== step: 4=============
current array(0, 0): []
first(0) == last(0): true, so min = 1
=================== step: 5=============
current array(1, 1): []
first(1) == last(1): true, so min = 4
compare min of step[4] and step[5]: 1 < 4 = true, so min = 1
=================== step: 6=============
current array(2, 2): []
first(2) == last(2): true, so min = 7
compare min of step[5] and step[6]: 1 < 7 = true, so min = 1
=================== step: 7=============
current array(3, 5): [8, 5]
first(3) == last(5): false, so divide 2 the array
=================== step: 8=============
current array(3, 4): [8]
first(3) == last(4): false, so divide 2 the array
=================== step: 9=============
current array(3, 3): []
first(3) == last(3): true, so min = 8
=================== step: 10=============
current array(4, 4): []
first(4) == last(4): true, so min = 5
compare min of step[9] and step[10]: 8 < 5 = false, so min = 5
=================== step: 11=============
current array(5, 5): []
first(5) == last(5): true, so min = 2
compare min of step[10] and step[11]: 5 < 2 = false, so min = 2
compare min of step[6] and step[11]: 1 < 2 = true, so min = 1
min is: 1
我目前正在学习数据结构并正在学习递归。下面发布的 code/algorithm 应该使用递归找到数组的最小值。但是，我无法理解它是如何工作的。我的老师的解释不是很有帮助，所以如果有人知道如何很好地解释这一点，我将不胜感激！
public class Recursive {
public static int minimum(int array[], int first, int last) {
int answer;
int mid;
int minFirst;
int minSecond;
if(first == last)
return array[first];
else {
mid = (first + last) / 2;
minFirst = minimum(array, first, mid);
minSecond = minimum(array, mid + 1, last);
}
if(minFirst < minSecond)
answer = minFirst;
else
answer = minSecond;
return answer;
}
}
为了更好地理解代码的工作原理，让我们放一些打印语句。这将告诉我们该方法的每次递归正在处理哪些数据。
我在代码中添加了一些注释。
public class Test {
public static void main(String[] args) throws Exception {
int[] arr = {4,3,2,1};
System.out.println("\nThe smallest element is : " +minimum(arr, 0, 3, 1));
}
//this method finds smallest element within given range in an array
public static int minimum(int array[], int first, int last, int indent) {
//lets print what each recursion is working on
int[] subArray = Arrays.copyOfRange(array, first, last+1);
System.out.println(" ".repeat(indent) + "Invoked with: first="
+ first + " last=" + last
+ " Array=" + Arrays.toString(subArray));
int answer;
int mid;
int minFirst;
int minSecond;
if(first == last) {
System.out.println(" ".repeat(indent) + "Selected " + array[first]);
return array[first];
}
else {
//divide the range in half
mid = (first + last) / 2;
//find smallest element from first half
minFirst = minimum(array, first, mid , indent + 3);
//find smallest element from second half
minSecond = minimum(array, mid + 1, last, indent +3);
}
//select smallest element from both halves
if(minFirst < minSecond)
answer = minFirst;
else
answer = minSecond;
System.out.println(" ".repeat(indent) + "Selected " + answer + " from " + minFirst + ", " + minSecond);
return answer;
}
}
输出：
Invoked with: first=0 last=3 Array=[4, 3, 2, 1]
Invoked with: first=0 last=1 Array=[4, 3]
Invoked with: first=0 last=0 Array=[4]
Selected 4
Invoked with: first=1 last=1 Array=[3]
Selected 3
Selected 3 from 4, 3
Invoked with: first=2 last=3 Array=[2, 1]
Invoked with: first=2 last=2 Array=[2]
Selected 2
Invoked with: first=3 last=3 Array=[1]
Selected 1
Selected 1 from 2, 1
Selected 1 from 3, 1
The smallest element is : 1
您也可以像 Eclipse 一样使用 IDE 的 debug feature。
该方法在 first 和last 指定的范围内查找数组中的最小元素。所以 minimum(arr, 4, 6) 会在 arr[4]、arr[5] 和 arr[6] 中找到最小值。
让我们看看它是如何做到的。
如果first与last相同，指定范围内只有一个元素，即array[first]（或array[last]，即一样）。最小的元素一定是那个元素，所以 return array[first].
否则，我们要将范围分成两半。为此，我们首先通过 (first + last) / 2 找到范围的中点 - 计算 first 和 last 的平均值。那么两半是：
- 从
first到mid - 从
mid + 1到last
然后我们找到每一半中的最小元素，因此：
minimum(array, first, mid)minimum(array, mid + 1, last)
我知道在我们还没有完成声明它的作用时如何使用 minimum 方法是违反直觉的，但是让我们相信自己 minimum 会做它应该做的- 找到最后两个参数指定的范围之间的最小值。
然后我们比较这些最小值。这些最小值中的较小者是整个范围内的最小元素（最后一个 if 语句在做什么）。
几乎每个递归算法都包含两个关键部分：
琐碎的案例
所有递归算法都会为微不足道的输入提供瞬时答案（并且不会递归）。
在这种特定情况下，简单的输入情况是当 'first' 和 'last' 彼此相等时：该方法的目的是 return 在其中找到的最小值从索引 'first' 开始到索引 'last' 结束的所有值。当 first 和 last 相等时，只有一个数字可供查看。那么，'what is the smallest number amongst this giant collection of.... 1 number' 就是……那个数字。那是微不足道的情况。
小案例的进展。
所有其他情况都通过首先再次调用您自己的方法来解决，但是使用修改后的输入 - 应该修改输入，以便它们以某种方式更接近边缘情况。有时，你多次调用自己的方法，但是 all 这样的调用必须保证 all 更接近普通情况，然后你组合单独的答案。
在这种情况下，问题表述为：
要从数字列表中找到最小的数字，首先，将数字列表分成大致相等的两部分。这些列表更小，因此也更简单，所以我们可以要求自己计算这些较小列表的答案 - 没关系，我们将它们移到了平凡的情况下，我们可以做到。然后，将获得的两个答案组合起来：只 return 最小的答案，将较大的答案分块。
就是这样。
这就是编写递归代码所需的全部内容。如果您从这些方面考虑它是有道理的：对于任何输入，该算法都是根据应用于计算稍微简单问题的结果的简单操作来重述问题。
那个稍微简单一点的问题的结果是用同样的方式完成的：通过对一个更简单的问题的计算结果应用一个简单的操作。
冲洗并重复直到问题非常简单，答案显而易见并且可以立即提供。
再补上log，大家可以看清楚了：
import java.util.Arrays;
import java.util.concurrent.atomic.AtomicInteger;
public class Recursive {
private static AtomicInteger step = new AtomicInteger();
public static int minimum(int array[], int first, int last) {
int answer;
int mid;
int minFirst;
int minSecond;
int currentStep = step.incrementAndGet();
System.out.println("=================== step: " + currentStep + "=============");
int[] currentArray = new int[last - first];
System.arraycopy(array, first, currentArray, 0, currentArray.length);
System.out.println("current array(" + first + ", " + last + "): " + Arrays.toString(currentArray));
System.out.print(String.format("first(%d) == last(%d): %b", first, last, first == last));
if(first == last) {
System.out.println(", so min = " + array[first]);
return array[first];
}
else {
System.out.println(", so divide 2 the array");
mid = (first + last) / 2;
minFirst = minimum(array, first, mid);
int minFirstStep = step.get();
minSecond = minimum(array, mid + 1, last);
int minSecondStep = step.get();
System.out.print(String.format("compare min of step[%d] and step[%d]: %d < %d = %b",
minFirstStep,
minSecondStep,
minFirst,
minSecond,
minFirst < minSecond));
}
if(minFirst < minSecond)
answer = minFirst;
else
answer = minSecond;
System.out.println(", so min = " + answer);
return answer;
}
public static void main(String[] args) {
int array[] = {1, 4, 7, 8, 5, 2};
int min = minimum(array, 0, array.length - 1);
System.out.println("min is: " + min);
}
}
输出：
=================== step: 1=============
current array(0, 5): [1, 4, 7, 8, 5]
first(0) == last(5): false, so divide 2 the array
=================== step: 2=============
current array(0, 2): [1, 4]
first(0) == last(2): false, so divide 2 the array
=================== step: 3=============
current array(0, 1): [1]
first(0) == last(1): false, so divide 2 the array
=================== step: 4=============
current array(0, 0): []
first(0) == last(0): true, so min = 1
=================== step: 5=============
current array(1, 1): []
first(1) == last(1): true, so min = 4
compare min of step[4] and step[5]: 1 < 4 = true, so min = 1
=================== step: 6=============
current array(2, 2): []
first(2) == last(2): true, so min = 7
compare min of step[5] and step[6]: 1 < 7 = true, so min = 1
=================== step: 7=============
current array(3, 5): [8, 5]
first(3) == last(5): false, so divide 2 the array
=================== step: 8=============
current array(3, 4): [8]
first(3) == last(4): false, so divide 2 the array
=================== step: 9=============
current array(3, 3): []
first(3) == last(3): true, so min = 8
=================== step: 10=============
current array(4, 4): []
first(4) == last(4): true, so min = 5
compare min of step[9] and step[10]: 8 < 5 = false, so min = 5
=================== step: 11=============
current array(5, 5): []
first(5) == last(5): true, so min = 2
compare min of step[10] and step[11]: 5 < 2 = false, so min = 2
compare min of step[6] and step[11]: 1 < 2 = true, so min = 1
min is: 1