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

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

18 голосов
/ 09 ноября 2010

У меня было домашнее задание, в котором запрашивалась функция, использующая прямую рекурсию для поиска индекса самого левого, самого низкого, отрицательного целого числа в массиве.Дополнительные требования заключались в том, чтобы параметры функции были массивом и размером, и чтобы возвращаемое значение для недопустимого значения было -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;
}

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

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

Примечание: мое домашнее задание уже сдано и оценено.

Ответы [ 6 ]

5 голосов
/ 09 ноября 2010

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

РЕДАКТИРОВАТЬ: Сказав это, если вы хотите сделать функцию хвоста рекурсивной: 

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)

РЕДАКТИРОВАТЬ2: поиск плохо обозначенного крайнего левого, наиболее отрицательного значения. Вы, вероятно, можете указать это в качестве индекса первого наиболее отрицательного значения.

РЕДАКТИРОВАТЬ3: удаление большинства условий, так как легче найти индекс наименьшего значения, а затем проверить, является ли он отрицательным.

1 голос
/ 10 ноября 2010

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

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

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

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

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

  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);
   }
};
1 голос
/ 10 ноября 2010

Вот как вы могли бы реализовать это, используя хвостовую рекурсию: 

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 выше).

1 голос
/ 09 ноября 2010

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

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);
}
0 голосов
/ 10 ноября 2010

Вы можете сделать это с двумя статиками ... 

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);
}
0 голосов
/ 10 ноября 2010

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

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» от значения «not found».Другие, вероятно, более читаемые, подходы будут включать использование дополнительных аккумуляторов для фактического минимального значения (вместо только индекса) и / или текущего смещения в массиве (так что обход может быть выполнен в «нормальном» порядке.Конечно, если бы я кодировал что-то подобное для серьезного использования, я бы не использовал рекурсию.

...