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.

You forgot to return the results of minimoddiff from the recursive function. You should have gotten a warning about it. If not, turn on compiler warnings, probably with -Wall. — Schwern
I wrote it in the text of the question! It works even without the return, that's not the probem; I'm asking how to optimize it to avoid passing the first "difference" from the main! — L. Repetti
Well, you have to have correct code before there is any point optimising it. "it works even without the return". Really? then what is the point of having that code if it is called and not returned? Might as well delete it right? — kaylum
You are surely more good than me in developing, I'm just at the start of a Computer Science Degree and out teacher said us that there isn't difference between returning the value and doing that, for the scope of the functions. I'm editing the text using return, thanks for the info. — L. Repetti
@L.Repetti You're using undefined behavior, the C standard's way of saying when it happens the compiler can do whatever it wants. Your compiler decided to guess at your intent and make it work. Others might not. In C "it works" means "it happens to work on my machine with this compiler and this phase of the moon, but it might not work on a different machine, or compiler, or phase of the moon." Unlike some other languages, C does not return the last evaluated expression. You cannot leave off the return and expect it to work. — Schwern

chux - Reinstate Monica chux - Reinstate Monica · Accepted Answer · 2017-01-27T03:15:03

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

C - Recursive function for minimum gap in array

3 Answers