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

Question

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

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

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

Примечание: мое домашнее задание уже было повернуто и градуировано.

Answer 1

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

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

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

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

Чтобы получить представление о, например, 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); 
    } 
}; 

Answer 2

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

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

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: удаление большинства условных обозначений, так как легче найти индекс самого низкого значения, а затем проверить, является ли оно отрицательным.

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

Answer 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 выше) только.

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

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

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