La ricorsione di coda è possibile se un confronto dipende dal valore di ritorno?

Question

Ho avuto un compito a casa che richiedeva una funzione che utilizza la ricorsione diretta per trovare l'indice del numero intero più basso, più a sinistra, negativo in un array. Ulteriori requisiti erano che i parametri della funzione fossero la matrice e la dimensione e che il valore di ritorno per nessun valore valido fosse -999.

sono arrivato fino a questo:

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

Funziona, soddisfa i requisiti, e mi ha fatto pieno credito. Questo può essere implementato con la ricorsione della coda?

Mi sembra che dal momento che devi prendere il risultato della chiamata ricorsiva da utilizzare in un confronto per decidere se passare quella o aggiornarlo che non sarebbe possibile, ma la ricorsione ancora mi lega il cervello fa un nodo così potrebbe esserci qualcosa di ovvio che mi manca.

Nota: il mio compito a casa era già stato consegnato e classificato.

Answer 1

È necessario memorizzare il numero più basso trovato finora da qualche parte. Con la tua funzione stai usando lo stack per memorizzarlo.

Con una funzione ricorsiva della coda è necessario memorizzare il numero più basso trovato finora altrove. ad esempio

• Come variabile globale (ugh ..).
• Come parametro per la funzione stessa.
• Come membro variabile

Il requisito che avete per la vostra funzione probabilmente esclude tutti coloro che, in modo si è lasciato con qualcosa come il codice che hai, che non può essere scritto per essere ricorsiva in coda.

Per avere un'idea di ad es. l'ultimo punto 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); 
    } 

E

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

Se si trasforma il risultato di ricorsione prima di tornare, non è ricorsivo in coda.

EDIT: Detto questo, se si vuole fare la funzione di coda ricorsiva:

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

E chiamare il più LowIndexMinNeg(src, src_size, src_size - 1)

EDIT2: trovare il valore più a sinistra più negativo mal definito. Probabilmente puoi dichiararlo come l'indice del primo valore più negativo.

EDIT3: rimozione della maggior parte dei condizionali, poiché è più facile trovare l'indice del valore più basso, quindi controllare se è negativo.

Answer 3

potrei avere una proposta, ma ovviamente ho dovuto cambiare la firma:

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

Ecco come si potrebbe implementare che l'utilizzo di ricorsione in coda:

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

Questa implementazione utilizza gli argomenti di default per mantenere la funzione tutti insieme, ma ciò crea un'interfaccia disordinata. È possibile dividere questo in due funzioni, se ti piace:

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

In questo caso, LowIndexMinNegHelper ha solo bisogno di essere una funzione locale (che ho indicato con static sopra).

Answer 5

non sono sicuro se le norme per l'assegnazione avrebbe consentito la definizione di una funzione ausiliaria, ma che è uno standard di trasformazione per il raggiungimento di ricorsione di coda quando la firma più naturale dell'operazione non lo consente. Per esempio:

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

Questa versione inverte anche l'ordine di attraversamento per consentire di distinguere il valore "reale" di 'min' dal valore 'non trovato'. Altri approcci, probabilmente più leggibili, comporterebbero l'uso di accumulatori aggiuntivi per il valore minimo effettivo (anziché solo un indice) e/o l'offset corrente nell'array (in modo che l'attraversamento possa essere fatto in ordine "normale". Certo se fossi codifica qualcosa di simile per l'uso serio non sarebbe utilizzando la ricorsione, in primo luogo.

Answer 6

Si potrebbe fare questo con due statica ...

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