Come riconoscere cos'è e cosa non è la ricorsione della coda?

Question

A volte è abbastanza semplice (se la chiamata è l'ultima, è una ricorsione di coda), ma ci sono ancora casi che mi confondono. Un professore mi ha detto che "se non ci sono istruzioni da eseguire dopo l'auto-chiamata, è una ricorsione di coda". Che ne dici di questi esempi (trascurare il fatto che non hanno molto senso):

a) Questo dovrebbe essere ricorsivo in coda, vedere come l'auto-chiamata è l'ultima affermazione, e non c'è nulla da eseguire dopo di esso .

function foo(n) 
{ 
    if(n == 0) 
     return 0; 
    else 
     return foo(n-2); 
} 

b) Ma che ne dici di questo? Dovrebbe essere una coda, perché se la condizione è vera, nulla sarà eseguito, ma non è l'ultima dichiarazione?

function foo(n) 
{ 
    if(n != 0) 
     return foo(n-2); 
    else 
     return 0; 
} 

c) Che ne dici di questo? In entrambi i casi, l'auto chiamata sarà l'ultima cosa eseguita:

function foo(n) 
{ 
    if(n == 0) 
     return 0; 
    else  
    { 
     if(n > 100) 
      return foo(n - 2); 
     else 
      return foo(n - 1); 
    } 
} 

Answer 1

Potrebbe aiutarti a pensare a questo in termini di come le ottimizzazioni di coda sono effettivamente implementate. Questo non fa parte della definizione, ovviamente, ma motiva la definizione.

In genere quando viene chiamata una funzione, il codice chiamante memorizzerà tutti i valori di registro di cui avrà bisogno in seguito, nello stack. Memorizzerà anche un indirizzo di ritorno, indicando l'istruzione successiva dopo la chiamata. Farà tutto ciò che è necessario per garantire che il puntatore dello stack sia impostato correttamente per il destinatario. Quindi salterà all'indirizzo di destinazione [*] (in questo caso, la stessa funzione). Al ritorno, sa che il valore di ritorno è nel posto specificato dalla convenzione di chiamata (registro o stack).

Per una chiamata di coda, il chiamante non lo fa. Ignora qualsiasi valore di registro, perché sa che non ne avrà più bisogno in seguito. Imposta il puntatore dello stack in modo che il callee utilizzi lo stesso stack del chiamante e non si imposta come indirizzo di ritorno, ma salta semplicemente all'indirizzo di destinazione.Così, il chiamato sovrascrive la stessa regione di stack, metterà il suo valore di ritorno nella stessa posizione in cui il chiamante avrebbe inserito il suo valore di ritorno, e quando ritorna, non ritornerà al suo chiamante, ma ritornerà al suo chiamante chiamante.

Pertanto, in modo informale, una funzione è ricorsiva in coda quando è possibile che si verifichi un'ottimizzazione della chiamata di coda e quando l'obiettivo della chiamata di coda è la funzione stessa. L'effetto è più o meno lo stesso come se la funzione contenesse un ciclo, e invece di chiamare se stesso, la chiamata di coda salta all'inizio del ciclo. Ciò significa che non ci devono essere variabili necessarie dopo la chiamata (e in effetti nessuna "operazione da fare", che in una lingua come C++ non significa nulla da distruggere), e il valore di ritorno della coda deve essere restituito dal chiamante.

Questo è tutto per la ricorsione di coda semplice/banale. Ci sono trasformazioni che possono essere usate per creare qualcosa di ricorsivo di coda che non è già, per esempio introducendo parametri extra, che memorizzano alcune informazioni usate dal livello di "più basso" di ricorsione, per fare un lavoro che altrimenti sarebbe fatto l'uscita". Così, per esempio:

int triangle(int n) { 
    if (n == 0) return 0; 
    return n + triangle(n-1); 
} 

può essere fatto ricorsiva in coda, sia da parte del programmatore o automaticamente da un compilatore abbastanza intelligente, in questo modo:

int triangle(int n, int accumulator = 0) { 
    if (n == 0) return accumulator; 
    return triangle(n-1, accumulator + n); 
} 

Pertanto, l'ex funzione potrebbe essere descritto come " coda ricorsiva "da qualcuno che sta parlando di un linguaggio/compilatore abbastanza intelligente. Preparati per quell'uso variante.

[*] La memorizzazione di un indirizzo di ritorno, lo spostamento del puntatore dello stack e il salto, possono o non possono essere racchiusi in un unico codice operativo dall'architettura, ma anche se ciò non accade normalmente.

Answer 2

Sì; Penso che il tuo professore abbia inteso questo in ogni percorso, se l'istruzione finale è ricorsiva, allora è una ricorsione di coda.

Quindi, tutti e tre gli esempi sono ricorsivi in ​​coda.

Answer 3

Tutte le funzioni sono ricorsive in coda.

nessuna istruzione a sinistra dopo l'auto-chiamata

significa: Dopo l'auto-chiamata, si ritorna dalla funzione, vale a dire non più di codice deve essere eseguita, e non che ci sia non più linea di codice nella funzione.

Answer 4

Tutti e tre gli esempi sono ricorsivi di coda. In generale, è una ricorsione di coda, se il risultato della funzione (l'espressione che segue la parola chiave "return") è una chiamata solitaria alla funzione stessa. Nessun altro operatore deve essere coinvolto nel livello più esterno dell'espressione. Se la chiamata a se stessa è solo una parte di un'espressione, allora la macchina deve eseguire la chiamata, ma deve ritornare nella valutazione di detta espressione, cioè, non era alla base dell'esecuzione della funzione ma nel mezzo di un espressione. Questo tuttavia non si applica a nessun parametro che la chiamata ricorsiva possa assumere: qualsiasi cosa è consentita lì, comprese le chiamate ricorsive a se stessa (ad esempio "return foo (foo (0));"). L'ottimizzazione delle chiamate ai salti è possibile solo per la chiamata esterna, ovviamente.