La recursión de cola es un subconjunto de recursión donde el valor devuelto se obtiene a través de una llamada de cola, es decir, lo último que hace una función es llamar a otra función.
Compare estos dos ejemplos:
public int factorial (int n) {
if (n <= 1) devuelve 1;
retorno n * factorial (n – 1);
}
- Cómo resolver el problema ALCATRAZ3 (The honeycomb maze) en SPOJ
- ¿Alguien puede ayudarme a encontrar el máximo divisor común entre dos enteros en Java?
- ¿Existe una versión del problema de la mochila en la que haya una restricción sobre qué objetos se pueden colocar en la bolsa?
- ¿Cuáles son los mejores libros sobre algoritmos que usan C ++?
- ¿Cuáles son los mejores algoritmos y estructuras de datos MOOC?
Esto no es una llamada de cola, porque el resultado del factorial se multiplica por algo, la llamada a la función no es la última operación.
public int factorial (int n) {
return tailFactorial (1, n);
}
private int tailFactorial (int acumulador, int n) {
si (n <= 1) devuelve el acumulador;
return tailFactorial (acumulador * n, n – 1);
}
Esta es una llamada de cola, porque el resultado de factorial se devuelve inmediatamente.
Entonces, ahora la pregunta es, ¿por qué molestarse? Y la respuesta es la optimización de llamada de cola: si la última acción de un método es una llamada a otro método, en lugar de crear un nuevo marco de pila para el contexto del nuevo método (argumentos, variables locales, etc.), podemos reemplazar El actual . Uno de los inconvenientes de los métodos recursivos normales es que son realmente abusivos para la pila de llamadas. La optimización de llamadas de cola elimina este problema y garantiza que el rendimiento de un algoritmo recursivo es exactamente tan bueno como su contraparte iterativa (aunque potencialmente es mucho más legible).
Es posible que desee dar un vistazo a Tail call – Wikipedia.
