Base de conocimientosCentro de exámenes
ESEspañol
Elegir idioma13

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

recursion

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.

Ú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.

Fuentes