♾️ Recursividad

Un método recursivo es un método que se llama a sí mismo.

Un método iterativo es un método que resuelve el problema sin llamarse a sí mismo.

Los métodos recursivos son útiles para resolver problemas que pueden descomponerse en subproblemas más pequeños y similares al problema original.

Su esctructura básica es

static int funcionRecursiva(){
    //...
    funcionRecursiva();
    //....
}

Definición de la función recursiva

Caso base: Una función recursiva tiene que tener una condición que permita no tener que llamarse a sí misma en algún caso, ya que puede producirse desbordamiento de pila(Stack Overflow) al no terminar nunca la función. Este es el caso base.

Reducción del problema: En cada llamada a la función, el problema debe ser de menor tamaño.

Ejemplo recursividad: Factorial: N!

Recordamos como se hacía el cálculo de n!:

n! = n * (n-1) * (n-2) * .... mientras n > 0

Además, 0! se define como 1.

Ejemplos:

• 4! = 4 * 3 * 2 * 1 = 24
• 3! = 3 * 2 * 1 = 6
• 1! = 1
• 0! = 1

Como vemos en el ejemplo, podemos deducir que el factorial se repite en términos de (n-1) y el único caso donde no se calcula el factorial es 0!, esto nos lleva a que:

0! = 1 → if n = 0 //caso base

n! = n * (n-1) → if n > 0 //reducción del problema

De forma que el factorial de un número quedaría codificado de la siguiente forma:

    public static int factorial(int n) {
        if (n == 0) {//caso base
            return 1;
        } else {//llamada recursiva que reduce el problema
            return n * factorial(n-1);
        }
    }

Traza

factorial(4)
    4 * factorial(3)
        3 * factorial(2)
            2 * factorial(1)
                1 * factorial(0)
                    return 1
                return 1 * 1 --> 1   
            return 2 * 1 --> 2
        return 3 * 2 --> 6 
    return 4 * 6 --> 24
return 24

EJEMPLO 2: Sumar los elementos de un array

Podemos tener una versión recursiva de la suma de los elementos de una array.

caso base

tamañoArray=0 ---> return 0;

reducción del problema

return array[tamaño-1]+ suma(array, tamaño-1)

public static int calcularSuma(int[] array, int n) {
    // Caso base: cuando el tamaño del array es 0, la suma es 0
    if (n == 0) {
        return 0;
    } else {
        // Llamada recursiva: sumar el último elemento con la suma de los elementos restantes
        return array[n - 1] + calcularSuma(array, n - 1);
    }
}

Importante

Algunos puntos importantes a tener en cuenta sobre los métodos recursivos en Java:

• Caso base: Debes asegurarte de tener un caso base en tu método recursivo. Este caso base define la condición en la que la recursión se detiene y la función comienza a devolver resultados.

• Problemas de desbordamiento de pila (Stack Overflow): Si no se controla adecuadamente, la recursión puede provocar un desbordamiento de la pila de llamadas (Stack Overflow). Esto ocurre cuando hay demasiadas llamadas recursivas anidadas. Es importante tener cuidado con esto y asegurarse de que haya un camino claro hacia el caso base.

• Eficiencia: Aunque los métodos recursivos pueden ser elegantes y concisos, a veces pueden ser menos eficientes que las soluciones iterativas. Esto se debe a que cada llamada recursiva implica un overhead adicional en términos de memoria y tiempo de ejecución.

• Claridad y legibilidad del código: A veces, un enfoque recursivo puede hacer que el código sea más fácil de entender, especialmente cuando el problema es intrínsecamente recursivo en su naturaleza. Numerosos problemas son difíciles de resolver con soluciones iterativas, y solo la solución recursiva conduce a la resolución del problema (por ejemplo, Torres de Hanoi o recorrido de Árboles)