nodos - pilas en java estructura de datos
Lograr la recursión sin pila en Java 8 (1)
Un trampolín es un patrón para convertir la recursión basada en la pila en un bucle equivalente. Dado que los bucles no agregan marcos de pila, esto puede pensarse como una forma de recursión sin pila.
Aquí hay un diagrama que encontré útil:
Puede pensar en un trampolín como un proceso que toma un valor inicial; itera en ese valor; y luego sale con el valor final.
Considere esta recursión basada en pila:
public static int factorial(final int n) {
if (n <= 1) {
return 1;
}
return n * factorial(n - 1);
}
Por cada llamada recursiva que hace esto, se empuja un nuevo marco. Esto se debe a que el marco anterior no se puede evaluar sin el resultado del nuevo marco. Esto se convertirá en un problema cuando la pila se profundice demasiado y nos quedemos sin memoria.
Afortunadamente, podemos expresar esta función como un bucle:
public static int factorial2(int n) {
int i = 1;
while (n > 1) {
i = i * n;
n--;
}
return i;
}
¿Que está pasando aqui? Hemos dado el paso recursivo y lo hemos convertido en la iteración dentro de un bucle. Realizamos un ciclo hasta completar todos los pasos recursivos, almacenando el resultado o cada iteración en una variable.
Esto es más eficiente ya que se crearán menos marcos. En lugar de almacenar un cuadro para cada llamada recursiva ( n cuadros), almacenamos el valor actual y el número de iteraciones restantes (2 valores).
La generalización de este patrón es un trampolín.
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();
}
}
El Trampoline requiere dos miembros:
- el valor del paso actual;
- la siguiente función para calcular, o nada si hemos llegado al último paso
Cualquier cálculo que se pueda describir de esta manera puede ser "trampolín".
¿Cómo se ve esto para el factorial?
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));
}
};
}
}
Y para llamar:
Factorial.createTrampoline(4, 1).compute()
Notas
- Boxing hará que esto sea ineficiente en Java.
- Este código fue escrito en SO; No ha sido probado ni compilado
Otras lecturas
¿Cómo logro la recursión sin apilamiento en Java?
La palabra que parece surgir más es "trampolín", y no tengo ni idea de lo que eso significa.
¿Podría alguien EN DETALLE explicar cómo lograr la recursión sin apilamiento en Java? Además, ¿qué es "trampolín"?
Si no puede proporcionar ninguno de estos, ¿podría indicarme la dirección correcta (es decir, un libro para leer sobre el tema o algún tutorial que enseñe todos estos conceptos)?