使用递归查找数组中的最小数？

Question

int i = 0;
int min = x[i];
while ( i < n ){
    if ( x[i] < min ){
        min = x[i];
    }
    i++;
}
return min;

我已经写了用迭代的形式寻找数组最小数字的方法。但是我想写一个递归函数来完成这个任务。请帮忙！

- user133466

---

列表是否已排序？如果是的话，递归可能更合理；否则，在这里使用递归似乎有些别扭。 - samoz

如果列表已经排序，第一个元素将是最小值，迭代和递归都没有意义。 - sepp2k

即使已经排序，最后一个元素也可能是最小值，这取决于排序的方式。 - Myles

让我们不要做任何假设，将列表视为未排序。 - Vikram

Answer 1

因为这个问题听起来像作业，所以这里有一个提示：数组中最小的值要么是第一个元素，要么是剩余数组中最小的数字，取两者中较小的一个。

- Greg Hewgill

---

请注意：这是否真的是家庭作业并不重要。如果您自己发现解决方案，您将比从别人那里复制解决方案获得更大的价值。这是一种练习方法。 - Greg Hewgill

Answer 2

这不是最优解，因为您可能会将递归调用的结果保存在int变量中，但我在练习中不被允许这样做。无论如何，该函数通过使用递归来搜索int数组中的最小值。首先它通过检查大小是否等于1来检查数组中有多少元素，并返回第一个值作为结果。如果表格大于1（并且从技术上讲也比较低），它将最后一个值与剩余的数组中的递归调用进行比较。递归在0索引处停止，然后将该值与索引1进行比较。然后将0和1索引的最小值与来自索引3的值进行比较，依此类推，直到达到最后一个值。

int minimum(int array[], int size) {
    if (size == 1) {
        return array[0];
    }
    else {
        return (array[size] < minimum(array, size - 1))
            ? array[size]
            : minimum(array, size - 1);
    }
}

int array[5] = {5, 99, 205, 1, 15};
int smallest = minimum(array, 4); // 4 = index of the last element

我的练习规则：

• 不要改变数组
• 不要使用任何变量
• 使用递归

- botder

---

你还应该写一些解释说明你所做的事情，以便初学者能够理解。 - Federico

@Federico，我一開始完全不知道如何解決我的練習題，即便參考這個網頁仍然束手無策。直到我自己找到了解決方案並決定在此發布。總之，我編輯了我的帖子並添加了一個解釋。 - botder

我的意见只是一个建议（带有一个错误：D显示->应该。该死的智能手机自动更正器），为了得到完整的答案。将来，如果您注释您的代码，那么我们会很感激，因为您可以更多地了解它。当然，这只是一个简单的练习，所以并不是非常重要，但这是一个初学者的问题，所以我认为提供一个初学者的答案是很好的。+1为努力加油 :) - Federico

Answer 3

单元素数组的最小值就是这个数组中唯一的那个数。

长度大于1的数组的最小值是第一个元素和剩余元素中的最小值中更小的那个。

（空数组没有定义最小值。）

- sepp2k

Answer 4

听起来像是作业，但你最好的选择是这样的：

int main(void) {
    int size = 2;
    int test[] = {0,1};
    int min = test[0];
    findMin(&min, test, size);
    printf("%d", min);
}

void findMin(int* min, int* test, int* length);

void findMin(int* min, int* test, int* length) {
    if (length >= 0) {
         if (*test < *min) {
            *min = test;
         }
         findMin(min, test++, (*length)--);
    }
}

- Myles

---

技术上是递归的，但缺乏整体性。 - Jim Zajkowski

Answer 5

这是一个函数，它将返回指向最小值的指针：

#include <stddef.h>

int *recursiveMin(int *x, int n) {
  if (x == NULL || n == 0)
      return NULL;
  if (n == 1)
      return x;
  int *t = recursiveMin(x + 1, n - 1);
  return *x < *t ? x : t;
}

- DigitalRoss

Answer 6

递归的一般规则是避免“小步骤”——因此，“将第一个元素与数组的其余部分进行比较”是非常糟糕的想法。尝试将数组分成两半进行处理，像这样：

min( array ) {
   if size of array == 1 return array[0]
   else if size of array == 2 return array[0] < array[1] ? array[0] : array[1]
   else {
      firstmin = min( firsthalf) // stored to avoid double calls
      secondmin = min( secondhalf)
      firstmin < second_min ? firstmin : secondmin
   }
 }

为了进一步优化：
- 避免数组复制 - 考虑使用类似快速排序的签名（数组，起始位置，结束位置）
- 对于大小小于2的情况，避免递归调用。

- Frantisek Kossuth

---

在10个答案中，这是唯一一个开始智能地执行递归的答案。+1 - chux - Reinstate Monica

Answer 7

#include <iostream>
#include <cstdlib>
using namespace std;

int min(int [], int);
void mostrar(int [], int);

int main() {
    int f[] = {4, 9, 0, -1, 5, 8, -3, 6, -4, 0};
    int t = sizeof(f)/sizeof(int);
    cout << "\nEl valor m\xa1nimo para los valores:\n";
    mostrar(f, t);
    cout << "\nes: " << min(f, t);
    system("pause>nul");
}

int min(int x[], int p) {
    if (p == 1)
        return x[0];
    int aux = min(x+1, p-1);
    return x[0] < aux ? x[0] : aux;
}

void mostrar(int v[], int k) {
    if (k > 1)
        mostrar(v, k-1);
    cout << v[k-1] << " ";
}

- H. Murcia

Answer 8

这是伪代码

ALGORITHM Unknown (A[0,...,n-1] )
if n=1 then
return A[0]
else
temp<- Unknown (A[0,...,n-2] )
if temp<= A[n-1] then
return temp
else return A[n-1]

- Rasathurai Karan

Answer 9

public int arrayMinValue(int[] array){
    if(array.length == 1)
        return array[0];
    else
    {
        int valor = array[array.length-1];
        int[] newArray = Arrays.copyOf(array, array.length-1);
        Integer mun = arrayMinValue(newArray);
        return mun <= valor? mun : valor;
    }
}

- fvalds2011

Answer 10

尝试：

  int recursive_min(list<int> arr) {
    return recursive_min(arr);
  }

虽然这在命令式语言中不起作用。

更严肃的答案是，以伪代码形式：

func recursive_min( list l ) {
 head = l[1]
 tail = l[2<->end]
 if l.length==1 return head else return min(head,recursive_min(tail))
}

虽然如果 l 为空则无法运行。

- Jack V.