Finding the Minimum Element of an Array Using Tail-Recursion

Question

Given an integer array a of size n, write a tail-recursive function with prototype

int f(int a[], int n);

that finds the minimum element of the array.

This is the best I managed to come up with:

int f(int a[], int n)
{
   static int *min;

   if (min == 0)
      min = new int(a[n - 1]);
   else if (*min > a[n - 1])
      *min = a[n - 1];

   if (n == 1)
      return *min;
   else
      return f(a, n - 1);
}

Can it get better? I do not like the use of a static variable.

You can do a ton better. The thing in recursion that isn't easily grasped (therefore exploited) is the use of the stack to hold temporary values along the way. Think about that for a minute. — WhozCraig
– WhozCraig, Commented Nov 28, 2012 at 1:51
@WhozCraig not as fun as seeking something drastic in an already-optimal alg. go as recursive as you like. he's been getting too much reaction to his code. — ashley
– ashley, Commented Nov 28, 2012 at 2:59

kmkaplan · Accepted Answer · 2012-11-28 01:53:20Z

17

int f(int a[], int n)
{
    if (n == 1)
        return a[0];
    n--;
    return f(a + (a[0] > a[n]), n);
}

answered Nov 28, 2012 at 1:53

kmkaplan

19k4 gold badges55 silver badges65 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

WhozCraig Over a year ago

it moves the starting point of the array up by one in the recursed call if a[0] in the current stack frame is larger than a[n]. Its also quite ingenious. I wish I could up-vote it more than once.

kmkaplan Over a year ago

@JosuéMolina This is C, there is no boolean: the result of a[0] > a[n] is either 0 or 1. It is like (a[0] > a[n]) ? (a + 1) : a

chrisaycock Over a year ago

@JosuéMolina It's pointer arithmetic. By adding 1 to the pointer, the recursive step will get the next spot in the array. That is, if the current value (a[0]) is greater than the last value, then the current value can't be the smallest element, so might as well try the next one. Otherwise, we stay with the current value until we've "shrunk" the array (n--). What we're left with is the smallest value.

WhozCraig Over a year ago

The only way this pukes is if the grader passes in a value < 1 for the size (no specification on zero-length arrays was given in the question, however. but it is the only chance of being marked down for what is otherwise a beatiful answer).

WhozCraig Over a year ago

Exactly. what do you return on n<1 ? you can't deref the array obviously. throw an exception?? =P. Chalk it up to an instructor that didn't define the problem with all boundaries accounted. None-the-less, your solution is outstanding. Love an elegant recursion solution.

|

Nik Bougalis · Accepted Answer · 2012-11-28 02:29:04Z

2

kmkaplan's solution is awesome, and I upvoted him. This would have been my not as awesome solution:

int f(int a[], int n)
{
    if(n == 1)
        return a[0];

    n--;

    if(a[0] > a[n])
        a[0] = a[n];

    return f(a, n);
}

The smallest element of the array, at any given time, is stored in a[0]. I originally included a non-modifying version, but then it occurred to me that it was not tail-recursive.

edited Nov 28, 2012 at 2:29

answered Nov 28, 2012 at 2:22

Nik Bougalis

10.7k1 gold badge24 silver badges38 bronze badges

Collectives™ on Stack Overflow

Finding the Minimum Element of an Array Using Tail-Recursion

2 Answers 2

9 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

9 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related