La domanda breve è: cosa può qualificarsi per l'ottimizzazione della ricorsione della coda (TCO) o l'eliminazione della ricorsione della coda (TRE) se il compilatore o l'interprete lo supporta.
Il riassunto di questa domanda è nella sezione " O è vero che, un modo più semplice di pensarci " di seguito.
Ho visualizzato la domanda Stack Overflow "Cos'è l'eliminazione coda-ricorsione?" pure, e leggere diverse descrizioni di come una ricorsione chiamata coda può accadere.
Primo:
a tail call is a subroutine call performed as the final action of a procedure (Wikipedia as of Jan 10, 2016)
Secondo:
when the value returned by the recursive call is itself immediately returned (Programming Interview Exposed, Wiley, 2013)
Terzo:
when a function calls itself, it cannot do any operation with this value that involves a local variable, and just return it. This call happens at the end of function, and so any local variables or "state" inside the stack (inside the current scope) can be thrown away
Penso che il secondo sia molto vicino al terzo, tranne che non ho visto esattamente cosa significa "immediatamente". Il primo mi ha fatto pensare che se restituisco n * fact(n-1) allora si qualifica, anche se più avanti in Wikipedia, dice che n * fact(n - 1) non è ricorsivo di coda, perché anche se si chiama sull'ultima riga, usa n , quindi non ha i requisiti per il TCO.
È interessante notare che forse il libro Programming Interview Exposed 2013, Wiley, ha bisogno di un'errata, che dice
int factorial( int n ) {
if (n > 1) {
/* Recursive case */
return factorial(n-1) * n;
} else {
/* Base case */
return 1;
}
}
when the value returned by the recursive call is itself immediately returned, as in the preceding definition for factorial, the function is tail-recursive. Some compilers can perform tail call elimination on tail-recursive functions, an optimization that reuses the same stack frame for each recursive call
ma non penso che sia ricorsivo in coda, vero?
È importante chiamare l'ultima riga? Nella pagina Tail Call Optimization in Ruby si dice che il seguente codice può essere qualificato per il TCO:
def fact(n, acc=1) # just assuming we pass in non-negative n
return acc if n <= 1
return fact(n-1, n*acc)
end
Ma non è vero che anche i seguenti si qualificano per il TCO?
def fact(n, acc=1)
return fact(n-1, n*acc) if n > 1
return acc if n <= 1
end
O non lo è, perché ha "affari incompiuti" - hai bisogno dello stack per ricordare dove il codice ha raggiunto e continua in seguito, quindi non puoi cancellare lo stack?
Che cosa succede se esegui operazioni matematiche, ma è come return 1 + fact(n-1) ? Cioè, stai aggiungendo una costante, 1 invece di toccare qualsiasi variabile locale, quindi non ci dovrebbero essere informazioni sullo stack che devono essere conservate ogni volta che ricorre. Ma se lo visualizzi come se avessi bisogno di ricordare 1 + (1 + (1 + (1 + ... , in effetti avrai ancora bisogno di più stack, a meno che il tipico TCO possa effettivamente ottimizzarlo a 4 + fact(...) senza bisogno di nuovi stack.
O è vero che, un modo più semplice di pensarci è:
Quando riesci a cancellare l'intero frame dello stack, perché non è necessario conservare nessuna di queste informazioni nello stack corrente quando effettui la chiamata ricorsiva, puoi cancellare l'intero frame dello stack e usare solo un "GO" TO ", invece di aggiungere un nuovo stack, può qualificarsi per il TCO? Quindi, almeno per questa chiamata ricorsiva, non ci sarà overflow dello stack.
Quindi, se è possibile cancellare l'intero frame dello stack, ciò significa che non sono necessarie variabili locali?
Che cosa succede se si tratta di una chiamata ricorsiva per attraversare un albero binario o rinominare tutti i file in una directory e tutte le relative sottodirectory, dal modulo "Programming_Ruby.pdf" a "Programming Ruby.pdf", e la ricorsione non è sul ultima riga, perché l'ultima riga ha un print "this folder done" ... quindi, puoi cancellare l'intero frame dello stack? Cioè, la posizione della prossima linea di codice da eseguire dipenderà anche dal frame dello stack?
Se la linea successiva da eseguire dipende dallo stack, allora forse può ridursi a queste 2 regole?
-
la chiamata ricorsiva deve essere l'ultima operazione della funzione, quindi dopo questa chiamata ricorsiva, la funzione corrente terminerà e non ci sarà alcuna "riga successiva di codice da eseguire" da ricordare.
-
non ci devono essere operazioni coinvolte con questa chiamata ricorsiva. Nessuna operazione matematica, qualunque sia, soprattutto se coinvolge una variabile locale. Deve semplicemente
return f(...)e restituirlo da solo . (o chiama questa procedura da solo). Il...interno può comportare calcoli, anche se coinvolge variabili locali. Al di fuori di(...)non puoi fare alcun calcolo.