Возможно ли рекурсия хвоста, если сравнение зависит от возвращаемого значения?

У меня было задание домашней работы, в котором попросила функцию, которая использует прямую рекурсию, чтобы найти индекс самого левого, самого низкого и отрицательного целых чисел в массиве. Дополнительные требования были для параметров функции как массива и размера, а возвращаемое значение для допустимого значения было -999.

Я придумал это:

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

Он работает, удовлетворяет требованиям и получает полную защиту. Может ли это быть реализовано с хвостовой рекурсией?

Мне кажется, что, поскольку вы должны принять результат от рекурсивного вызова, чтобы использовать его в сравнении, чтобы решить, передаете ли вы его или обновите, что это будет невозможно, но рекурсия все еще связывает мой мозг сучками а это может быть что-то очевидное, что мне не хватает.

Примечание: мое домашнее задание уже было включено и оценено.

Ответ 1

Вам нужно сохранить наименьшее число, найденное до сих пор. С помощью вашей функции вы используете стек чтобы сохранить это.

С хвостовой рекурсивной функцией вам нужно будет сохранить самое низкое число, найденное до сих пор в другом месте. например:

Как глобальная переменная (ugh..).
В качестве параметра самой функции.
В качестве переменной-члена

Требование, которое у вас есть для вашей функции, вероятно, исключает все это, поэтому у вас осталось что-то вроде кода, который у вас есть, который нельзя записать как хвост-рекурсивный.

Чтобы получить представление о, например, вторая последняя точка:

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

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

Ответ 2

Если вы вернете результат рекурсии перед возвратом, он не будет рекурсивным.

EDIT: Сказав это, если вы хотите сделать функцию tail рекурсивной:

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

И назовите LowIndexMinNeg(src, src_size, src_size - 1)

EDIT2: поиск плохо названного самого левого самого отрицательного значения. Вероятно, вы можете указать это как индекс первого наиболее отрицательного значения.

EDIT3: удаление большинства условных обозначений, так как легче найти индекс самого низкого значения, а затем проверить, является ли оно отрицательным.

Ответ 3

У меня могло бы быть предложение, но, конечно, мне пришлось изменить подпись:

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

  const int min_value = (min == -999) ? 0 : src[min];
  return LowIndexMinNeg(src, size - 1, src[size - 1] <= min_value ? size - 1 : min);
}

Ответ 4

Здесь вы можете реализовать это с помощью рекурсии хвоста:

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

В этой реализации используются аргументы по умолчанию, чтобы поддерживать функцию вместе, но это создает беспорядочный интерфейс. Вы можете разделить это на две функции, если хотите:

static int LowIndexMinNegHelper(int src[], int size, int index, int lowest_index, int lowest_value)
{
    if (index >= size) {
        return lowest_index;
    }
    if (src[index] < lowest_value) {
        return LowIndexMinNegHelper(src, size, index+1, index, src[index]);
    } else {
        return LowIndexMinNegHelper(src, size, index+1, lowest_index, lowest_value);
    }
}


int LowIndexMinNeg(int src[], int size)
{
    return LowIndexMinNegHelper(src, size, 0, -999, 0);
}

В этом случае LowIndexMinNegHelper должна быть только локальная функция (которую я указал с помощью static выше).

Ответ 5

Я не уверен, разрешили ли правила для назначения определять вспомогательную функцию, но это одно стандартное преобразование для достижения хвостовой рекурсии, когда сама естественная сигнатура операции не позволяет этого. Например:

int LowIndexMinNeg2(int src[], int size, int min)
{
    if (size == 0) return min;
    src--; size--; 
    if (min >= 0) min++;

    if (src[0] < 0
    && (min < 0 || src[0] <= src[min])) 
        min = 0;

    return LowIndexMinNeg2(src, size, min);
} 

int LowIndexMinNeg2(int src[], int size)
{
    return LowIndexMinNeg2(src + size, size, -999);
}

Эта версия также отменяет порядок обхода, чтобы можно было отличить "реальное" значение "min" от значения "не найдено". Другие, вероятно, более читаемые подходы будут включать в себя использование дополнительных аккумуляторов для фактического минимального значения (вместо только индекса) и/или текущего смещения в массиве (так что обход может выполняться в "нормальном" порядке. Конечно, если бы я использовал что-то вроде этого для серьезного использования, я бы не использовал рекурсию в первую очередь.

Ответ 6

Вы можете сделать это с помощью двух статики...

int LowIndexMinNeg(int src[], int size)
{
  static int _min = 0;
  static int _index = 0;

  if (size == 0) return -999;
  if (_index == size) return (src[_min] < 0) ? _min : -999;
  if (src[_index] < 0 && src[_index] < src[_min]) _min = _index;
  ++_index;
  return LowIndexMinNeg(src, size);
}