CODEWITHSUNDEEP
c
Steve
Steve

Reputation: 31

Finding minimum value of array from a certain point

I'm trying to make a recursive function that will return the smallest value of an array after a certain point which will be inputted into the function.

This needs to be done recursively without using loops.

This is what I have so far:

#include <stdio.h>

int findMinpos(int arr[], int mid, int len){
  int minimum;
  if(len==1)
    return arr[0+mid];

  else {
    minimum = findMinpos(arr, mid, len-1);
    if(minimum<arr[len-1])
      return minimum;
    else
      return arr[len-1];
  }
}

int main(void) {
  int array[7]= {23,17,8,7,9,32,56};
  printf("%d", findMinpos(array, 2, 7));
  return 0;
}

I'm not sure what I'm doing wrong, I could use some help.

Upvotes: 0

Views: 114

Answers (2)

Schwern
Schwern

Reputation: 165145

I suspect this is homework to teach how to approach problems with Divide and Conquer. This splits a problem up into two simpler subproblems which are then solved recursively. It's usually useful for sorting and searching.

Simply finding the smallest element in a list is overkill, it's O(nlogn) where a simple loop would be O(n), but it's teaching the technique. I hope.

In this case you find the smallest element of an array by splitting it in two halves, finding the smallest element of those halves, and then taking minimum of those. You keep splitting until you have just one element, that terminates the recursion.

@chux already wrote the code, there's no need for me to repeat that.

Why they want you to do it starting from a certain index doesn't make a lot of sense. I suspect what you're really supposed to do is use the midpoint to split the array in half and recurse like so...

int findMin(int arr[], int start, int len) {
  assert(len > 0);
  if(len == 1 ) {
    return arr[start];
  }
  int mid = len/2;
  int left_min = findMin(arr, start, mid);
  int right_min = findMin(arr, mid, len - mid);
  return left_min < right_min ? left_min : right_min;
}

int main(void) {
  int array[7]= {23,17,8,7,9,32,56};
  printf("%d\n", findMin(array, 0, 7));
}

This avoids having to do pointer arithmetic. Pointer arithmetic is generally faster and simpler, but often it doesn't get taught until later.

Upvotes: 1

chux
chux

Reputation: 154210

mid is never updated.

Code "works" with the test case by luck.

This needs to be done recursively without using loops.

Of course recursion is not required, nor advisable, to find the min int.

Although called mid, the findMinpos(arr, mid, len-1) implies code will call findMinpos() N times (N is the original array element count) and makes for a recursion depth O(N).

Such linear use of recursion, give recursions a bad name.

Instead, halve the problem each findMinpos call.

int findMinpos_alt(int arr[], int len){
  assert(len > 0);
  if(len == 1 ) {
    return arr[0];
  }
  int left_len = len/2
  int left_min =  findMinpos_alt(arr, left_len);
  int right_min =  findMinpos_alt(arr + left_len, len - left_len);
  return left_min < right_min ? left_min : right_min;
}

This calls the function N times, yet the recursion depth is O(log(N)).

More advanced code would use

int findMinpos_alt2(const int arr[], size_t len);

Upvotes: 2

Related Questions