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

Ответ 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);
}