Czy rekursja ogona jest możliwa, jeśli porównanie zależy od wartości zwracanej?

Question

Miałem zadanie domowe, które poprosiło o funkcję, która używa bezpośredniej rekurencji do znalezienia indeksu najniższej, najniższej, ujemnej liczby całkowitej w tablicy. Dodatkowe wymagania dotyczyły parametrów funkcji jako tablicy i rozmiaru, a wartością zwracaną bez ważnej wartości było -999.

wymyśliłem to:

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

To działa, spełnia wymagania, i załatwił mi pełny kredyt. Czy można to zrealizować za pomocą rekursji ogonowej?

Wydaje mi się, że ponieważ musisz wziąć wynik z rekursywnego wezwania do użycia w porównaniu, aby zdecydować, czy przekazujesz go lub aktualizujesz, że nie będzie to możliwe, ale rekursja nadal wiąże mój mózg z Węszy to, więc może być coś oczywistego, czego mi brakuje.

Uwaga: Moje zadanie domowe zostało już włączone i ocenione.

Answer 1

Musisz przechowywać najniższą gdzieś znalezioną do tej pory. Za pomocą swojej funkcji używasz stosu do przechowywania tego.

Przy pomocy funkcji rekursywnej ogona należy zapisać najniższą liczbę znalezioną dotychczas w innym miejscu. np .:

• Jako zmienna globalna (ugh ..).
• Jako parametr do samej funkcji.
• Jako członek zmiennej

Wymóg masz do swojej funkcji prawdopodobnie wyklucza tych wszystkich, więc jesteś w lewo z czymś w rodzaju kodu masz, które nie mogą być zapisywane za ogon rekurencyjnej.

Aby zorientować się np. W 2 Ostatni punkt:

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

I

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

Jeśli zmienisz wynik rekursji przed powrotem, to nie będzie ona rekursywna.

EDIT: Mimo, że jeśli chcesz, aby funkcja rekurencyjna ogon:

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

I zadzwonić jako LowIndexMinNeg(src, src_size, src_size - 1)

EDIT2: znalezienie słabo określany jako wartość od lewej najbardziej negatywny. Można prawdopodobnie stwierdzić, że jako indeks pierwszej najbardziej ujemnej wartości.

EDIT3: usunięcie większości warunków warunkowych, ponieważ łatwiej jest znaleźć indeks najniższej wartości, a następnie sprawdzić, czy jest ujemny.

Answer 3

Może mam propozycję, ale oczywiście musiałem zmienić podpis:

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

Oto jak można zaimplementować, że za pomocą ogona rekurencji:

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

Implementacja ta używa domyślnych argumentów zachowaj tę funkcję razem, ale to sprawia, że ​​interfejs jest niechlujny. Można podzielić to na dwie funkcje, jeśli chcesz:

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

W tym przypadku LowIndexMinNegHelper tylko musi być lokalną funkcję (co ja z static wskazanego powyżej).

Answer 5

Nie jestem pewien, czy przepisy dotyczące cesji byłby dozwolony definiując funkcję pomocniczą, ale to jest jedna standardowa transformacja do osiągnięcia rekurencji ogon gdy jest najbardziej naturalny podpis operacji nie pozwala na to. Na przykład:

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

Ta wersja również odwraca kolejność przechodzenia aby umożliwić odróżnienie „prawdziwą” wartość „min” od „nie znaleziono” wartości. Inne, prawdopodobnie bardziej czytelne podejścia wymagałyby użycia dodatkowych akumulatorów dla rzeczywistej wartości minimalnej (zamiast tylko indeksu) i/lub prądu przesuniętego w macierzy (tak, że przemieszczenie można wykonać w "normalnej" kolejności. Oczywiście gdybym coś takiego poważnego zastosowania kodowania nie byłbym za pomocą rekurencji w pierwszej kolejności.

Answer 6

można to zrobić z dwóch statyki ...

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