Un trampolino è un modello per trasformare la ricorsione basata sullo stack in un loop equivalente. Poiché i loop non aggiungono frame di stack, questo può essere pensato come una forma di ricorsione senza stack.
Ecco un diagramma che ho trovato utile:
Da bartdesmet.net
Si può pensare a un trampolino come un processo che richiede un valore iniziale; itera su quel valore; e poi esce con il valore finale.
considerare questa ricorsione stack-based:
public static int factorial(final int n) {
if (n <= 1) {
return 1;
}
return n * factorial(n - 1);
}
Per ogni chiamata ricorsiva questo fa, un nuovo frame viene spinto. Questo perché il frame precedente non può valutare senza il risultato del nuovo frame. Questo diventerà un problema quando lo stack diventa troppo profondo e abbiamo esaurito la memoria.
Per fortuna, possiamo esprimere questa funzione come un ciclo:
public static int factorial2(int n) {
int i = 1;
while (n > 1) {
i = i * n;
n--;
}
return i;
}
cosa sta succedendo qui? Abbiamo preso il passaggio ricorsivo e ne abbiamo fatto l'iterazione all'interno di un ciclo. Effettuiamo un ciclo fino a quando non abbiamo completato tutti i passaggi ricorsivi, memorizzando il risultato o ogni iterazione in una variabile.
Questo è più efficiente poiché verranno creati meno fotogrammi. Invece di memorizzare una cornice per ogni chiamata ricorsiva (n frame), memorizziamo il valore corrente e il numero di iterazioni rimanenti (2 valori).
La generalizzazione di questo modello è un trampolino.
public class Trampoline<T>
{
public T getValue() {
throw new RuntimeException("Not implemented");
}
public Optional<Trampoline<T>> nextTrampoline() {
return Optional.empty();
}
public final T compute() {
Trampoline<T> trampoline = this;
while (trampoline.nextTrampoline().isPresent()) {
trampoline = trampoline.nextTrampoline().get();
}
return trampoline.getValue();
}
}
Il Trampoline richiede due componenti:
- il valore del passo corrente;
- la funzione di fianco a calcolare, o nulla se abbiamo raggiunto l'ultimo passo
Qualunque calcolo che può essere descritto in questo modo può essere "trampolined".
Che aspetto ha per fattoriale?
public final class Factorial
{
public static Trampoline<Integer> createTrampoline(final int n, final int sum)
{
if (n == 1) {
return new Trampoline<Integer>() {
public Integer getValue() { return sum; }
};
}
return new Trampoline<Integer>() {
public Optional<Trampoline<Integer>> nextTrampoline() {
return Optional.of(createTrampoline(n - 1, sum * n));
}
};
}
}
E per chiamare:
Factorial.createTrampoline(4, 1).compute()
Note
- Boxing farà questo inefficiente in Java.
- Questo codice è stato scritto su SO; non è stato testato o addirittura compilato
Letture
[Questa domanda] (http://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration) potrebbe essere un inizio utile, come potrebbe [questa risposta ] (http://programmers.stackexchange.com/a/194708) sui programmatori, che tocca sui trampolini –
dare un'occhiata a questo thread su implementazioni trampolino: [http://stackoverflow.com/questions/189725/what -is-a-trampoline-function] (http://stackoverflow.com/questions/189725/what-is-a-trampoline-function) –