设计一个查找数组最小值的递归算法

Question

我在考虑递归算法（这是一个理论问题，所以编程语言并不重要）。 它包括寻找一组数字中的最小值

我当时是这样想的：设“n”为集合中元素的个数。让我们将集合重新排列为：

(a, (b, c, ..., z) ).

函数从左向右移动，第一个元素在第一阶段被假定为最小值（当然是第0个元素a）。接下来的步骤定义如下：

(a, min(b, c, ..., z) )，检查a是否仍然是最小值，或者b是否被假定为最小值，则(a or b, min(c, d , ..., z) ), 另一个检查条件, (a or b or c, min(d, e, ..., z)), 检查条件等

我想理论上的伪代码可能如下：

f(x) {

// base case 
if I've reached the last element, assume it's a possible minimum, and check if y < z. then return a value to stop recursive calls.  
// inductive steps
if ( f(i-th element) < f(i+1, next element) ) { 
/* just assume the current element is the current minimum */ 
} 
}

我在处理基本情况时遇到了问题。我不知道如何将其形式化。我想我已经理解了它的基本思想：它基本上就是我在伪代码中编写的内容，对吗？

到目前为止我写的内容有意义吗？抱歉，如果不清楚，但我是初学者，而且我是第一次学习递归，我个人觉得它很混乱。所以，我已经尽力解释了。如果不清楚，请告诉我，我会尝试用不同的词更好地解释它。

Answer 1

对我来说，更像是这样：

int f(int[] x)
{
    var minimum = head of X;
    if (x has tail)
    {
        var remainder = f(tail of x);
        if (remainder < minimum)
        {
            minimum = remainder;
        }
    }
    return minimum;
}

Answer 2

这是您提出的问题的递归解决方案，使用 JavaScript:

a = [5,12,3,5,34,12]

const min = a => {
  if (!a.length) { return 0 }
    if (a.length === 1) { return a[0] }
    return Math.min(a[0], min(a.slice(1)))
}

min(a)

注意方法是首先检测最简单的情况（空数组），然后是更复杂的情况（单元素数组），最后是递归调用，它将更复杂的情况减少为更简单的情况的函数。

但是，您不需要递归来遍历一维数组。

Answer 3

你的想法是对的。

您观察到的是正确的

min_recursive(array) = min(array[0], min_recursive(array[1:]))

该函数不关心谁在调用它或它之外发生了什么 -- 它只需要 return 传入的数组的最小值。基本情况是数组有一个单一价值。该值是数组的最小值，因此它应该只是 return 它。否则通过再次调用自身找到数组其余部分的最小值，并将结果与数组的头部进行比较。

其他答案显示了一些编码示例。

Answer 4

递归问题很难形象化。让我们举个例子：arr = [3,5,1,6]

这是一个相对较小的数组，但仍然不容易想象递归如何从头到尾在这里工作。

提示 : 尝试减小输入的大小。这将使可视化变得容易，并帮助您找到 base case。首先决定我们的功能应该做什么。在我们的例子中，它从数组中找到最小数字。如果我们的函数适用于大小为 n 的数组，那么它也应该适用于大小为 n-1 的数组（递归信念飞跃）。现在使用它我们可以减少输入的大小，直到我们不能进一步减少它，这应该给我们我们的基本情况。

让我们用上面的例子：arr = [3,5,1,6]

让我们创建一个函数 findMin(arr, start)，它接受一个数组和一个起始索引以及 returns 从起始索引到数组结尾的最小数字。

1st Iteration : [3,5,1,6]
// arr[start] = 3, If we can somehow find minimum from the remaining array,
// then we can compare it with current element and return the minimum of the two.
// so our input is now reduced to the remaining array [5,1,6]

2nd Iteration : [5,1,6]
// arr[start] = 5, If we can somehow find minimum from the remaining array,
// then we can compare it with current element and return the minimum of the two.
// so our input is now reduced to the remaining array [1,6]

3rd Iteration : [1,6]
// arr[start] = 1, If we can somehow find minimum from the remaining array,
// then we can compare it with current element and return the minimum of the two.
// so our input is now reduced to the remaining array [6]

4th Iteration : [6]
// arr[start] = 6, Since it is the only element in the array, it is the minimum.
// This is our base case as we cannot reduce the input any further.
// We will simply return 6.

------------ Tracking Back ------------

3rd Iteration : [1,6]
// 1 will be compared with whatever the 4th Iteration returned (6 in this case).
// This iteration will return minimum(1, 4th Iteration) => minimum(1,6) => 1 

2nd Iteration : [5,1,6]
// 5 will be compared with whatever the 3th Iteration returned (1 in this case).
// This iteration will return minimum(5, 3rd Iteration) => minimum(5,1) => 1 

1st Iteration : [3,5,1,6]
// 3 will be compared with whatever the 2nd Iteration returned (1 in this case).
// This iteration will return minimum(3, 2nd Iteration) => minimum(3,1) => 1 

Final answer = 1

function findMin(arr, start) {
  if (start === arr.length - 1) return arr[start];
  return Math.min(arr[start], findMin(arr, start + 1));
}

const arr = [3, 5, 1, 6];
const min = findMin(arr, 0);
console.log('Minimum element = ', min);

这是一道适合初学者练习递归的好题。你也可以尝试这些问题来练习。

使用递归反转字符串。
使用递归反转堆栈。
使用递归对堆栈进行排序。

设计一个查找数组最小值的递归算法

design a recursive algorithm that find the minimum of an array

algorithm

recursion