Tail Recursion - Tensho97/Aprende-a-Aprender GitHub Wiki

Supongamos el siguiente ejemplo:

public class Principal {
	public static void main(String[] args){
	       int number = 1;
		int max = 10000;
	    
	    squareAndPrintFail(number, max);
	 }

public static int squareAndPrintFail(int number, int max) {
		System.out.println(number * number);
		if (max > number)
			return squareAndPrintFail(number + 1, max);
		else
			return number;
		}
}

Si bien el ejemplo anterior cumple con la definición de Tail Call Optimization(TCO), toda la lógica es resulta antes de volver a llamarse así mismo, la Maquina Virtual de Java (JVM) va a lanzar una excepción del tipo java.lang.StackOverflowError.

Esto se debe a que el compilador de java no soporta directamente el TCO. Sin embargo, es posible implementarlo a partir de Java 8 con el uso de expresiones Lambda e Interfaces Funcionales.

El ejemplo anterior quedaría de la siguiente forma:

@FunctionalInterface
public interface TailCall {
	
	  TailCall get();
	  
	  default boolean terminated() { 
		  return false; 
	  }
}

public class TailCallTerminate implements TailCall {

	@Override
	public TailCall get() {
		  throw new Error("Don't call"); 
	}
	
	public boolean terminated() { 
		return true; 
	}
}

public static void main(String[] args) throws Exception {
		int number = 1;
		int max = 10000;
	    
	    Stream.iterate(squareAndPrint(1, max), TailCall::get)
	    .filter(TailCall::terminated)
	    .findFirst();
	  }

	public static TailCall squareAndPrint(int number, int max) {
		System.out.println(number * number);
		if(max > number) 
		return () -> squareAndPrint(number + 1, max);
		 else 
		      return new TailCallTerminate();
	}

Tenemos por un lado la interfaz TailCall y su implementación TailCallTerminate. Mediante el método get recibimos y ejecutamos la expresión Lambda y con el método terminated() controlamos cuando debemos detener la recursividad.

Por otro lado tenemos el método squareAndPrint al cual recibe dos parámetros que serán comparados para determinar para determinar si nuevamente ejecutamos el método o regresamos el TailCallTerminate.

Para ejecutar nuestro metodo squareAndPrint nos apoyamos en la clase Stream, la cual va a iterar hasta que en nuestro filtro encontremos una instancia TailCallTerminate y regresaremos como Optional el primer elemento de nuestro contenedor.

---

---

Autor: Richard