¿Cuáles son los beneficios de usar la recursividad de la cola? ¿Es siempre posible?

La recursividad de cola elimina el espacio de pila O (n) requerido para almacenar argumentos de función en la memoria cuando se realizan llamadas recursivas; la “n” aquí se refiere al número de llamadas recursivas realizadas antes de llegar al caso base. Convierte ese espacio de pila O (n) en espacio de pila O (1) reutilizando el marco de pila para cada llamada recursiva en lugar de crear uno nuevo para cada llamada. Si bien esta es una gran optimización de espacio, no siempre es posible; La recursión de cola solo se aplica si no hay instrucciones que siguen a la llamada recursiva.

Considere el siguiente código trivial para imprimir una cadena un carácter a la vez:

impresión vacía pública (String s) {
if (s.length () == 0) {return; }
System.out.println (s.charAt (0));
print (s.substring (1)); / * Corta el primer personaje * /
}

Observe cómo la llamada recursiva a la función print () es la última; de ahí proviene la “cola” en “recursión de cola”. El compilador verá esto y se dará cuenta de que no tiene sentido almacenar la pila de llamadas de función en la memoria porque no la necesitamos.

Ahora considere este código trivial para imprimir una cadena un carácter a la vez en reversa :

public void printReverse (String s) {
if (s.length () == 0) {return; }
printReverse (s.substring (1)); / * Corta el primer personaje * /
System.out.println (s.charAt (0));
}

Tenga en cuenta que todo lo que hemos hecho es intercambiar las líneas 3 y 4 del código. En este caso, el compilador se da cuenta de que hay instrucciones que siguen a la llamada recursiva; en otras palabras, la pila de llamadas a funciones debe recordarse para que podamos recordar a dónde regresar una vez que se haya ejecutado la instrucción posterior.

PD

Tenga en cuenta que estos fragmentos de código se usan solo para demostraciones simples de recursión. No tome estos fragmentos como ejemplos de buenas prácticas de codificación; Esta no es la forma óptima de implementar estas funciones.