CODEWITHSUNDEEP
carraysrecursion
user3393266
user3393266

Reputation: 59

Recursively splitting an array in C

I'm trying to come up with a divide-and-conquer algorithm for finding the minimum element in an array but recursive code is a bit mind bending to me.

For example, taking the following pseudo code:

 procedure R_MIN (A, n) 
 begin 
 if (n = 1) then 
     min := A[0]; 
 else 
     lmin := R_MIN (A, n/2); 
     rmin := R_MIN (&(A[n/2]), n - n/2); 
     if (lmin < rmin) then 
         min := lmin; 
     else 
         min := rmin; 
     endelse; 
 endelse; 
 return min; 
 end R_MIN

The way I understand it is we split the array in half, unless we have the base case. Then we figure out which half has the min and repeat the call, further splitting it (now we have 4 arrays). But where and how is the min actually found and what would this code look like in C? It seems to me this would only work when we have split into pairs.

Upvotes: 0

Views: 3614

Answers (2)

SomeWittyUsername
SomeWittyUsername

Reputation: 18358

Recursion is usually better understood from taking a bit of distance. You need to find the minimum in the array. If you split the big array in two halves, the minimum would be the minimum of each half minimum. That's the key concept here. And that's exactly what the code does. It's natural to wonder how this "magic" happens and the dwelling into it can be not so easy. However, it's not needed in most cases. Under the hood the principle of splitting into two halves is repeated without any additional intervention (that's the point of recursion - calling the same code again and again). And it stops at the base case - when there is only one number left so the minimum is the number itself (it could've been written to stop when 2 numbers are left, like you noted - but that's not needed and would force to do an explicit compare as the last step, adding complexity to the code).

Upvotes: 1

abacles
abacles

Reputation: 859

It finds the minimum from the previous recursive calls on the left and right halves of the array. When the base case is reached and the array has length 1, then that is the minimum of that sub-array of length 1. This minimum is then taken and compared with the minimum of the other half. The lower of the two is the minimum of this sub-array. This is returned to be compared and so on...

If you translate the pseudo-code to C:

#include <stdio.h>

int rec_min(int A [],int len)
{
  int min,lmin,rmin;
  if(len==1)
    return A[0];
  else
  {
    lmin=rec_min(A,len/2);
    rmin=rec_min(A+len/2,len-len/2);
    if(lmin<rmin)
      return lmin;
    else
      return rmin;
  }
}

int main()
{        
  int test [10]={3,2,7,4,5,8,1,9,6,10};

  printf("%d\n",rec_min(test,10));

  return 0;
}

Upvotes: 1

Related Questions