Anche se spesso si vede il seguente come un esempio di conversione fattoriale alla coda-call:
int factorial(int n, int acc=1) {
if (n <= 1) return acc;
else return factorial(n-1, n*acc);
}
non è del tutto corretto, in quanto richiede la moltiplicazione di essere sia associativa e commutativa. (Moltiplicazione è associativa e commutativa, ma quanto sopra non servire da modello per altre operazioni che non soddisfano tali vincoli.) Una soluzione migliore potrebbe essere:
int factorial(int n, int k=1, int acc=1) {
if (n == 0) return acc;
else return factorial(n-1, k+1, acc*k);
}
Questo serve anche come un modello per il Fibonacci trasformare:
int fibonacci(int n, int a=1, int b=0) {
if (n == 0) return a;
else return fibonacci(n-1, a+b, a);
}
Si noti che questi calcolare la sequenza a partire dall'inizio, al contrario di fare la fila in attesa di continuazioni in uno stack di chiamate. Quindi sono strutturalmente più simili alla soluzione iterativa rispetto alla soluzione ricorsiva. A differenza del programma iterativo, però, non modificano mai alcuna variabile; tutti i collegamenti sono costanti.Questa è una proprietà interessante e utile; in questi casi semplici non fa molta differenza, ma la scrittura di codice senza riassegnazioni semplifica alcune ottimizzazioni del compilatore.
Ad ogni modo, l'ultimo fornisce un modello per la funzione ricorsiva; come la sequenza di Fibonacci, abbiamo bisogno di mantenere le relative valori del passato, ma abbiamo bisogno di tre di loro invece di due:
int mouse(int n, int a=1, int b=1, int c=1) {
if (n <=2) return a;
else return mouse(n-1, a*c+1, a, b);
}
Addenda
Nei commenti, due questioni sono state sollevate. Proverò a risponderle (e un'altra ancora) qui.
In primo luogo, dovrebbe essere chiaro (da una considerazione dell'architettura della macchina sottostante che non ha concetto di chiamata di funzione) che qualsiasi chiamata di funzione può essere riformulata come goto (possibilmente con memoria intermedia non limitata); inoltre, qualsiasi goto può essere espresso come un tail-call. Quindi è possibile (ma non necessariamente carino) riscrivere qualsiasi ricorsione come ricorsione in coda.
Il solito meccanismo è "stile di passaggio continuo" che è un modo elegante per dire che ogni volta che si desidera chiamare una funzione, si impacchetta invece il resto della funzione corrente come una nuova funzione (la "continuazione") e passare quella continuazione alla funzione chiamata. Poiché ogni funzione riceve una continuazione come argomento, deve terminare ogni continuazione creata con una chiamata alla continuazione ricevuta.
Questo è probabilmente sufficiente per far girare la testa, quindi lo metto in un altro modo: invece di spingere gli argomenti e una posizione di ritorno nello stack e chiamando una funzione (che poi tornerà), si spingono gli argomenti e una continuazione posizione sullo stack e goto una funzione, che successivamente andrà alla posizione di continuazione. In breve, devi semplicemente rendere lo stack un parametro esplicito, e quindi non hai mai bisogno di tornare. Questo stile di programmazione è comune nel codice event-driven (vedi Python Twisted), ed è un vero dolore scrivere (e leggere). Quindi consiglio vivamente di lasciare che i compilatori eseguano questa trasformazione per te, se puoi trovarne uno che lo farà.
@xxmouse mi ha suggerito di estrarre l'equazione di ricorsione da un cappello e di chiedere come è stata ricavata. E 'semplicemente la ricorsione originale, ma riformulato come una trasformazione di una singola tupla:
fn = fn-1*fn-3 + 1
=>
Fn = <Fn-11*Fn-13+1, Fn-11, Fn-12>
Non so se questo è più chiaro, ma è il meglio che posso fare. Guarda l'esempio di Fibonacci per un caso leggermente più semplice.
@j_random_hacker chiede quali sono i limiti di questa trasformazione. Funziona per una sequenza ricorsiva in cui ogni elemento può essere espresso da una formula degli elementi precedenti, dove k è una costante. Esistono altri modi per produrre una ricorsione di coda. Ad esempio:
// For didactic purposes only
bool is_odd(int n) { return n%2 == 1; }
int power(int x, int n, int acc=1) {
if (n == 0) return acc;
else if (is_odd(n)) return power(x, n-1, acc*x);
else return power(x*x, n/2, acc);
}
Quanto sopra non uguale al solito non tail-call ricorsione, che fa una sequenza diversa (ma equivalente e altrettanto lunga) di moltiplicazioni.
int squared(n) { return n * n; }
int power(int x, int n) {
if (n == 0) return 1;
else if (is_odd(n)) return x * power(x, n-1));
else return squared(power(x, n/2));
}
Grazie a Alexey Frunze per il seguente test: uscita (ideone): la risposta di
mouse(0) = 1
mouse(1) = 1
mouse(2) = 1
mouse(3) = 2
mouse(4) = 3
mouse(5) = 4
mouse(6) = 9
mouse(7) = 28
mouse(8) = 113
mouse(9) = 1018
vero ricorsione di coda richiede di gestire sia la pila da soli, scriverlo in assemblea, o avere il supporto del compilatore. Non credo che Perl attualmente lo supporti. – Dai
Penso che @Dai sei confuso con la ricorsione della coda _removal_, che è un'ottimizzazione del compilatore. Stavo solo chiedendo di convertire in una funzione ricorsiva della coda, penso. – Gene