C-数组中最小间隙的递归函数

Question

我正在尝试优化一个函数，给定一个N int数组，它返回一个元素和前一个元素之间的最小差异。显然，该函数仅适用于具有维度的数组

#include <stdio.h>
#define N 4
/*Function for the difference, works because in the main I already gives one difference*/
int minimodiff(int *a, int n, int diff) {
  if (n==1) {
    return diff;
  }
  if (diff>(*(a+1) - *a))
     return minimodiff(a+1, n-1, *(a+1)-*a);
  else return minimodiff(a+1, n-1, diff);
}

int main() {
  int a[N]= {1,8,4,3};
  printf("%d", minimodiff(a+1, N-1, *(a+1)-*a));
}

不知道有没有办法避免在main中传递第一个差，而是在递归函数中做所有的事情。我可以用stdio . h/stdlib . h/string . h/math . h作为头文件。非常感谢你的帮助，我希望这能让我对递归函数有更好的理解。

Answer 1

递归方法是个坏主意，因为使用了额外的内存和函数调用
无论如何，你的问题是如何避免第一个差异
您可以使用百分位数
由于参数diff是一个int变量，因此不可能获得大于int_MAX的值
因此，可以通过将值INT_MAX作为diff对应的参数来完成对minimodiff的第一次调用。
此外，标准头限制。h必须在顶部#included，以使INT_MAX宏可见。

Answer 2

递归或其他方式进行min计算时，如果您将min设置为可能的最高值，则初始条件会更简单。如果您使用浮点数，它将是Infinity。由于您使用的是整数，因此它是INT_MAX，来自限制. h，它被定义为可能的最高整数。它保证大于或等于所有其他整数。

如果您使用循环迭代地执行此操作，您最初会设置diff=INT_MAX。由于这是递归，因此INT_MAX是递归完成时返回的内容。

#include <limits.h>

static inline int min( const int a, const int b ) {
    return a < b ? a : b;
}

int minimodiff( const int *a, const size_t size ) {
    if( size <= 1 ) {
        return INT_MAX;
    }

    int diff = a[1] - a[0];
    return min( minimodiff(a+1, size-1), diff );
}

Answer 3

< code>minimodiff(a 1，N-1，*(a 1)-*a)是一种使用递归的弱方法，因为它使用的递归深度为< code>N，这很容易超过系统资源深度限制。在这种情况下，一个简单的循环就足够了。

一个好的递归方法可以在每次调用时将问题减半，找到左半部分和右半部分的最小值。它可能不会运行得更快，但递归的最大深度将是 log2（N）。

// n is the number of array elements 
int minimodiff2(const int *a, size_t n) {
  if (n == 2) {
    return a[1] - a[0]; 
  } else if (n <= 1) {
    return INT_MAX;
  }
  int left = minimodiff2(a, n/2 + 1);  // +1 to include a[n/2] in both halves
  int right = minimodiff2(a + n/2, n - n/2);
  return (left < right) ? left : right;
}

int main() {
  int a[]= {1,8,4,3};
  printf("%d", minimodiff2(a, sizeof a/ sizeof a[0]));
}