CKTIS / Java
Recursión y pila de llamadas
Recursión y pila de llamadas: Hay recursión cuando un método se llama directa o indirectamente; cada invocación tiene su frame de pila, por lo que hacen falta caso base y progreso.
Versión: Java SE 21 (JLS and Java SE API); examples verified on the repository Java runtime
Sintaxis
recursionHay recursión cuando un método se llama directa o indirectamente; cada invocación tiene su frame de pila, por lo que hacen falta caso base y progreso.
Úsala para árboles acotados y divide y vencerás; sustituye un recorrido lineal profundo por iteración con Deque.
Java no garantiza optimización de llamadas de cola, así que una recursión correcta pero profunda puede acabar en StackOverflowError.
La entrada vacía debe alcanzar el caso base y un grafo cíclico necesita un conjunto de visitados para terminar.
Dos casos base terminan las llamadas: factorial(5) imprime 120 y el algoritmo de Euclides recursivo gcd(48,18) imprime 6.
Ejemplos
public class Main {
static int factorial(int n) {
return n <= 1 ? 1 : n * factorial(n - 1);
}
static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
public static void main(String[] args) {
System.out.println(factorial(5));
System.out.println(gcd(48, 18));
}
}
Resultado
120 6
Dos casos base terminan las llamadas: factorial(5) imprime 120 y el algoritmo de Euclides recursivo gcd(48,18) imprime 6.