数组中的MInimum元素(C)

Question

我是一个新手，无论是在这里的堆栈溢出，还是在编程世界。

今天，我正在解决一些关于递归的练习，其中一个要求编写一个递归函数来查找数组的最小元素。

经过多次尝试，我终于编写了这个工作代码，但我想问您这是否是一个“好的”代码。我是说，事实是它在一边，写得好吗？有什么需要改变的吗？而且，最重要的是，有一种方法可以使这个函数正常工作，而不必声明全局int "min"？:)

下面是代码：

#include <stdio.h>

int recursiveMinimum(int array[], size_t size);

int min = 1000;

int main(void) {
  int array[] = {55, 5, 1, 27, 95, 2};

  printf("\nMinimum element of this array is: %d\n\n",
         recursiveMinimum(array, 6));
}

int recursiveMinimum(int array[], size_t size) {
  if (size == 1) {
    return min;
  } else {
    if (array[size] <= min) min = array[size];
    return min = recursiveMinimum(array, size - 1);
  }
}

Answer 1

当函数依赖于全局变量时，这是个坏主意。

但是在任何情况下，您的函数都是不正确的，并调用未定义的行为。

在函数的第一个调用中，这个if语句

if (array[size] <= min) min = array[size];

尝试访问传递数组之外的内存，因为有效的索引范围是[0, size)。

此外，数组还可以包含大于全局变量初始值的所有元素。

int min = 1000;

由于变量min的值未指定，因此可能不会再次调用该函数。

函数应该返回数组中最小元素的索引。通常，用户可以传递等于0的第二个参数。在这种情况下，如果尝试返回空数组中不存在的元素，则函数将调用未定义的行为。

该函数可以通过以下方式声明和定义

size_t recursiveMinimum( const int a[], size_t n ) 
{
    if ( n < 2 )
    {
        return 0;
    }
    else
    {
        size_t min1 = recursiveMinimum( a, n / 2 );
        size_t min2 = recursiveMinimum( a + n / 2, n - n / 2 ) + n / 2;

        return a[min2] < a[min1] ? min2 : min1;
    }
}

这是一个演示程序

#include <stdio.h>

size_t recursiveMinimum( const int a[], size_t n )
{
    if (n < 2)
    {
        return 0;
    }
    else
    {
        size_t min1 = recursiveMinimum( a, n / 2 );
        size_t min2 = recursiveMinimum( a + n / 2, n - n / 2 ) + n / 2;

        return a[min2] < a[min1] ? min2 : min1;
    }
}

int main( void )
{
    int a[] = { 55, 5, 1, 27, 95, 2 };
    const size_t N = sizeof( a ) / sizeof( *a );

    size_t min = recursiveMinimum( a, N );

    printf( "\nMinimum element of this array is: %d at the position %zu\n",
            a[min], min );
}

程序输出是

Minimum element of this array is: 1 at the position 2

注意，第一个参数具有限定符const，因为传递的数组在函数中没有被更改。为了减少递归调用的次数，函数调用数组的两部分。

Answer 2

递归的工作方式是将调用时的大小缩小到下一次迭代，并将调用的结果与当前值进行比较，并返回2中较低的值。

作为递归停止，您可以简单地返回第一个元素

int recursiveMinimum(int array[], size_t size) {
  if (size == 1) return array[0];
  int min_of_rest = recursiveMinimum(array, size - 1);
  if (array[size - 1] <= min_of_rest) return array[size - 1];
  return min_of_rest;
}

完整示例：https://godbolt.org/z/sjnh8sYz3

Answer 3

在过去，我们用指针，KR风格来实现它.

严苛地使用指针是当时处理编译器效率低下的一种手段。

现在还不确定这是否被认为是好做法。下面是一个例子。

无论如何，以非递归的方式实现它会更好(更容易和更有效)。

#include <stdio.h>
void recursiveMinimum(int *array, size_t size, int *min) {
    if (size == 0) return;
    if (*array < *min) *min = *array;
    recursiveMinimum (array+1, size-1, min);
    return;
}
int main(void) {
    int array[] = {55, 5, 1, 27, 95, 2};
    size_t size = sizeof(array)/sizeof(*array);
    int min = array[0];
    recursiveMinimum (array, size, &min); 
    printf("\nMinimum element of this array is: %d\n", min);
    return 0;
}