C - Recursive function for minimum gap in array

Question

I'm trying to optimize a function that, given an array of N int, return the minimum difference between an element and the previous one. Obviously the function is just for array with a dimension >=2. For example, given the array {2,5,1}, function returns -4 . I tried to write my code, but I think it is really intricate.

#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));
}

I wonder if there is a way to avoid to pass the first difference in main, but doing everything in the recursive function. I can use as header file stdio.h / stdlib.h / string.h / math.h . Thanks a lot for the help, I hope that this can give me a better understanding of the recursive functions.

Answer 1

minimodiff(a+1, N-1, *(a+1)-*a) is a weak approach to use recursion for it uses a recursion depths of N which can easily overwhelm system resources depth limit. In such a case, a simple loop would suffice.

A good recursive approach would halve the problem at each call, finding the minimum of the left half and the right half. It may not run faster, but the maximum depth of recursion would be 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]));
}