Is tail recursion possible if a comparison depends on the return value?

Question

I had a homework assignment that asked for a function that uses direct recursion to find the index of the left-most, lowest, negative integer in an array. Additional requirements were for the parameters of the function to be the array and the size and that the return value for no valid value was -999.

I came up with this:

int LowIndexMinNeg(int src[], int size)
{
    if (size == 0)
       return -999;
    int index = LowIndexMinNeg(src, size - 1);

    if (index >= 0)
       return (src[size - 1] < src[index]) ? (size - 1) : index;
    else
       return (src[size - 1] < 0) ? (size - 1) : index;
} 

It works, satisfies the requirements, and got me full credit. Can this be implemented with tail recursion?

It seems to me that since you have to take the result from the recursive call to use in a comparison to decide if you pass that one on or update it that it wouldn't be possible but recursion still ties my brain in knots a it so there might be something obvious that I'm missing.

Note: My homework assignment was already turned in and graded.

Answer 1

If you transform the result of recursion before returning, it is not tail recursive.

EDIT: Having said that, if you want to make the function tail recursive:

const int SENTINEL= 0;

int LowIndexMinNeg(int src[], int size, int index)
{
    if (size == 0)
    {
        if (index<0 || src[index]>=0)
            return -999;
        else
            return index;
    }

    int current_index= size - 1;
    int new_index= src[current_index]<=src[index] ? current_index : index;

    return LowIndexMinNeg(src, size - 1, new_index);
} 

And call as LowIndexMinNeg(src, src_size, src_size - 1)

EDIT2: finding the poorly termed leftmost most negative value. You can probably state that as the index of the first most negative value.

EDIT3: removing most of the conditionals, since it's easier to find the index of the lowest value, then check if it's negative.

Answer 2

You need to store the lowest number found so far somewhere. With your function you're using the stack to store that.

With a tail recursive function you'll need to store the lowest number found so far elsewhere. e.g:

• As a global variable (ugh..).
• As a parameter to the function itself.
• As a member variable

The requirement you have for your function probably rules out all those, so you're left with something like the code you have, which cannot be written to be tail-recursive.

To get an idea of e.g. the 2 last point:

  int LowIndexMinNeg(int src[], int size,int current_lowest = 0,int lowest_index = 0) {
     if(size == 0)
        return current_lowest == 0 ? -999 : lowest_index;
     int val = src[size - 1] ;
     if(val < 0 && val  < current_lowest) {
        current_lowest = val;
        lowest_index = size -1;
     }
      return LowIndexMin(src,size - 1,current_lowest,lowest_index);
   }

And

struct find_smallest {
  int current_lowest = 0;
  int lowest_index = 0

   int LowIndexMinNeg(int src[], int size) {
     if(size == 0)
        return current_lowest == 0 ? -999 : lowest_index;
     int val = src[size - 1] ;
     if(val < 0 && val  < current_lowest) {
        current_lowest = val;
        lowest_index = size - 1;
     }
      return LowIndexMin(src,size - 1);
   }
};