♾️ 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)

Algoritmos clásicos que se resuelven con recursividad

1. Algoritmos de búsqueda y ordenación

• Búsqueda binaria: Se divide el array en dos mitades y se busca en la mitad correspondiente.
• Quicksort: Se elige un pivote, se ordenan los elementos menores y mayores recursivamente.
• Mergesort: Divide el array en dos mitades, ordena cada mitad y las combina.

2. Problemas de estructuras de datos

• Recorrido en árboles (DFS, preorden, inorden, postorden): Se exploran los nodos de un árbol de manera recursiva.
• Recorrido en grafos (DFS - Depth First Search): Similar a los árboles, se exploran los nodos de un grafo de manera recursiva.

3. Problemas matemáticos y combinatorios

• Cálculo del factorial: 𝑛!=𝑛×(𝑛−1)!n!=n×(n−1)!
• Cálculo del Fibonacci: F(n)=F(n−1)+F(n−2).
• Potencias
• Problema de la Torre de Hanói: Mover discos entre torres siguiendo reglas específicas.
• Generación de combinaciones y permutaciones: Útil en problemas de teoría de conjuntos.

4. Algoritmos en programación dinámica

Algunos problemas que pueden resolverse con programación dinámica usan una solución recursiva con almacenamiento en memoria intermedia:

• Número de formas de llegar a un punto en una escalera (similar a Fibonacci).
• Cambio de monedas: Contar de cuántas maneras se puede dar una cantidad con monedas de distintos valores.
• Problema de la mochila (Knapsack problem): Determinar qué objetos llevar en una mochila con capacidad limitada.

5. Problemas en juegos y puzzles

• Sudoku Solver: Resolver un Sudoku con backtracking recursivo.
• N-Reinas: Colocar N reinas en un tablero de ajedrez sin que se ataquen.
• Labyrinth Solver (Backtracking): Encontrar la salida en un laberinto.