Bienvenidos a esta clase donde vamos a explorar un concepto fascinante en programación: la recursividad. Imagina que tienes un espejo frente a otro, y en el reflejo del primer espejo ves otro espejo, y así sucesivamente. Para volverse loco, ¿verdad? Vamos a intentar comprender este concepto.

¿Qué es la recursividad?

La recursividad es un concepto fundamental en programación. La recursividad es una técnica de programación donde una función se llama a sí misma para resolver un problema. En Java, la recursividad se implementa mediante métodos. Puede ser que manejemos ambos conceptos (método y función) como sinónimos porque, en Java, el concepto de función no existe como tal: todo son métodos.

Este enfoque es útil para problemas que pueden dividirse en subproblemas más pequeños y similares al original. Suena un poco complicado, pero es realmente poderoso y te permite resolver problemas complejos de una manera elegante y concisa.

¿Cómo funciona la recursividad?

Una función recursiva consta de dos partes principales:

1. Caso Base: Es la condición que detiene la recursión. Sin un caso base, la función se llamaría indefinidamente, causando un error de desbordamiento de pila.
2. Caso Recursivo: Es la parte de la función donde se llama a sí misma con argumentos modificados, acercándose al caso base.

Ejemplo 1: contar hasta 10

Imagina que quieres contar hasta 10. En lugar de hacerlo de forma lineal, puedes usar la recursividad.

1. Caso base: Si el número actual es 10, terminas.
2. Caso recursivo: Si el número actual es menor que 10, imprimes el número actual y llamas a la función nuevamente, pero ahora con el número actual incrementado en 1.

Ejemplo en Java:

public class RecursionExample {

    public static void countUp(int n) {
        if (n == 10) {
            System.out.println(n);
        } else {
            System.out.println(n);
            countUp(n + 1);
        }
    }

    public static void main(String[] args) {
        countUp(1); // Comienza la recursión
    }
}

En este código:

• countUp(int n) es la función recursiva.
• if (n == 10) es el caso base. Si n es 10, la función termina.
• else es el caso recursivo. Se imprime n y se llama a countUp nuevamente con n + 1.

Ejemplo 2: Calcular una potencia

Calcular la potencia de un número ( a ) elevado a ( b ) (denotado como a^b , a^b o a**b, según el lenguaje) es un problema clásico que puede resolverse de manera recursiva. La idea es descomponer el problema en subproblemas más pequeños.

Caso base y caso recursivo:

1. Caso base: Cualquier número elevado a 0 es 1 (( a^0 = 1 )).
2. Caso recursivo: ( a^b = a \times a^{b-1} ).

Implementación en Java:

public class Potencia {
    // Método recursivo para calcular a^b
    public static double potencia(double a, int b) {
        // Caso base: a^0 = 1
        if (b == 0) {
            return 1;
        }
        // Caso recursivo: a^b = a * a^(b-1)
        else {
            return a * potencia(a, b - 1);
        }
    }

    public static void main(String[] args) {
        double base = 2;
        int exponente = 5;
        System.out.println(base + " elevado a " + exponente + " es: " + potencia(base, exponente));
    }
}

Explicación del código:

1. Caso base: Si el exponente ( b ) es 0, el método devuelve 1, ya que cualquier número elevado a 0 es 1.
2. Caso recursivo: Si ( b > 0 ), el método llama a potencia(a, b - 1) y multiplica el resultado por ( a ).

Ejemplo de ejecución:

Para ( a = 2 ) y ( b = 5 ):

• ( 2⁵ = 2 · 2⁴ )
• ( 2⁴ = 2 · 2³ )
• ( 2³ = 2 · 2² )
• ( 2² = 2 · 2¹ )
• ( 2¹ = 2 · 2⁰ )
• ( 2⁰ = 1 )

Finalmente, ( 2^5 = 32 ).

Ejemplo 3: Factorial de un Número

El factorial de un número entero positivo n se define como el producto de todos los números enteros positivos desde 1 hasta n. Por ejemplo, el factorial de 5 (denotado como 5!) es 5 × 4 × 3 × 2 × 1 = 120.

La definición matemática del factorial es:

• n! = 1, si n = 0 o n = 1 (caso base)
• n! = n × (n – 1)!, si n > 1 (caso recursivo)

Implementación en Java:

public class Factorial {
    // Método recursivo para calcular el factorial de un número
    public static int factorial(int n) {
        if (n == 0 || n == 1) {
            return 1; // Caso base: el factorial de 0 o 1 es 1
        } else {
            return n * factorial(n - 1); // Caso recursivo
        }
    }

    public static void main(String[] args) {
        int numero = 5;
        int resultado = factorial(numero);
        System.out.println("El factorial de " + numero + " es: " + resultado);
    }
}

Explicación del Código:

• Caso Base: Si n es 0 o 1, la función retorna 1, ya que el factorial de 0 y 1 es 1.
• Caso Recursivo: Si n es mayor que 1, la función se llama a sí misma con n - 1 y multiplica el resultado por n. Este proceso continúa hasta que se alcanza el caso base.

Ejecución Paso a Paso para n = 5:

1. factorial(5) llama a factorial(4)
2. factorial(4) llama a factorial(3)
3. factorial(3) llama a factorial(2)
4. factorial(2) llama a factorial(1)
5. factorial(1) retorna 1 (caso base)
6. factorial(2) retorna 2 × 1 = 2
7. factorial(3) retorna 3 × 2 = 6
8. factorial(4) retorna 4 × 6 = 24
9. factorial(5) retorna 5 × 24 = 120

Ejemplo 4: Secuencia de Fibonacci

La secuencia de Fibonacci es una serie de números donde cada número es la suma de los dos anteriores. Comienza con 0 y 1, y continúa indefinidamente: 0, 1, 1, 2, 3, 5, 8, …

Definición matemática:

• F(0) = 0 (caso base)
• F(1) = 1 (caso base)
• F(n) = F(n – 1) + F(n – 2), si n > 1 (caso recursivo)

Implementación en Java:

public class Fibonacci {
    // Método recursivo para calcular el n-ésimo número de Fibonacci
    public static int fibonacci(int n) {
        if (n == 0) {
            return 0; // Caso base: F(0) = 0
        } else if (n == 1) {
            return 1; // Caso base: F(1) = 1
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2); // Caso recursivo
        }
    }

    public static void main(String[] args) {
        int posicion = 6;
        int resultado = fibonacci(posicion);
        System.out.println("El número de Fibonacci en la posición " + posicion + " es: " + resultado);
    }
}

Explicación del Código:

• Casos Base: Si n es 0, la función retorna 0. Si n es 1, retorna 1.
• Caso Recursivo: Para n mayor que 1, la función retorna la suma de las dos llamadas recursivas anteriores: fibonacci(n - 1) y fibonacci(n - 2).

Ejecución Paso a Paso para n = 6:

1. fibonacci(6) llama a fibonacci(5) y fibonacci(4)
2. fibonacci(5) llama a fibonacci(4) y fibonacci(3)

Ejemplo 5: Listar Recursivamente una Carpeta

Listar recursivamente una carpeta implica recorrer todos los archivos y subcarpetas dentro de una carpeta dada. Este problema es ideal para la recursividad, ya que cada subcarpeta puede tratarse como una carpeta independiente.

Caso base y caso recursivo:

1. Caso base: Si el elemento es un archivo, se muestra su nombre.
2. Caso recursivo: Si el elemento es una carpeta, se listan sus archivos y subcarpetas.

Implementación en Java:

import java.io.File;

public class ListarCarpeta {
    // Método recursivo para listar archivos y carpetas
    public static void listarCarpeta(File carpeta, String indentacion) {
        // Verifica si la carpeta existe
        if (!carpeta.exists()) {
            System.out.println("La carpeta no existe.");
            return;
        }

        // Obtiene la lista de archivos y carpetas
        File[] elementos = carpeta.listFiles();

        // Recorre cada elemento
        if (elementos != null) {
            for (File elemento : elementos) {
                // Si es un archivo, muestra su nombre
                if (elemento.isFile()) {
                    System.out.println(indentacion + "Archivo: " + elemento.getName());
                }
                // Si es una carpeta, muestra su nombre y llama recursivamente
                else if (elemento.isDirectory()) {
                    System.out.println(indentacion + "Carpeta: " + elemento.getName());
                    listarCarpeta(elemento, indentacion + "  "); // Añade indentación
                }
            }
        }
    }

    public static void main(String[] args) {
        // Ruta de la carpeta a listar
        File carpeta = new File("ruta/a/la/carpeta");
        // Llama al método recursivo
        listarCarpeta(carpeta, "");
    }
}

Explicación del código:

1. Verificación de existencia: El método verifica si la carpeta existe. Si no existe, muestra un mensaje y termina.
2. Listado de elementos: Obtiene la lista de archivos y carpetas dentro de la carpeta actual.
3. Recorrido recursivo:

• Si el elemento es un archivo, muestra su nombre.
• Si el elemento es una carpeta, muestra su nombre y llama recursivamente a listarCarpeta para listar su contenido.

1. Indentación: Se usa para mejorar la legibilidad, mostrando la estructura de carpetas y subcarpetas.

Ejemplo de ejecución:

Supongamos que tenemos la siguiente estructura de carpetas:

CarpetaPrincipal/
├── Archivo1.txt
├── Archivo2.txt
└── SubCarpeta/
    ├── Archivo3.txt
    └── Archivo4.txt

El programa mostrará:

Carpeta: CarpetaPrincipal
  Archivo: Archivo1.txt
  Archivo: Archivo2.txt
  Carpeta: SubCarpeta
    Archivo: Archivo3.txt
    Archivo: Archivo4.txt

¿Por qué usar la recursividad?

• Facilita la comprensión y la claridad del código: Los algoritmos recursivos suelen ser más fáciles de entender, de leer y escribir.
• Simplifica problemas complejos: Algunos problemas, como los de divide y vencerás, se resuelven de manera natural con recursividad. Convierte así problemas complejos en soluciones más sencillas.
• Única forma de solucionar algunos problemas: A veces, la recursividad es la única forma de resolver una tarea, como por ejemplo listar una carpeta y sus posibles subcarpetas, y así sucesivamente. Precisamente a esto se llama listar una carpeta recursivamente.
• Aplicaciones en estructuras de datos: La recursividad es esencial para trabajar con estructuras como árboles y grafos.
• Eficiencia en ciertos casos: Puede ser más eficiente que los bucles iterativos en algunas situaciones. Aunque, la mayoría de las veces, los bucles iterativos son más eficientes que usar la recursividad.

Recursividad vs Iteración

La recursividad y la iteración (bucles como for o while) son técnicas complementarias. Aunque la recursividad es más elegante en algunos casos, la iteración suele ser más eficiente en términos de memoria y tiempo.

Ejemplo de factorial con iteración:

public class FactorialIterativo {
    public static int factorial(int n) {
        int resultado = 1;
        for (int i = 1; i <= n; i++) {
            resultado *= i;
        }
        return resultado;
    }

    public static void main(String[] args) {
        int numero = 5;
        System.out.println("El factorial de " + numero + " es: " + factorial(numero));
    }
}

Comparación:

En resumen

La recursividad es una herramienta poderosa en Java que permite resolver problemas de manera elegante y eficiente. Aunque puede ser menos eficiente que la iteración, su claridad y aplicabilidad en problemas complejos la hacen indispensable en la programación.

La clave está en identificar el caso base y el caso recursivo, y asegurarse de que cada llamada recursiva avance hacia el caso base. Con práctica, podrás dominar esta técnica y aplicarla en situaciones más complejas.

Consejos para usar recursividad

1. Define claramente el caso base: Sin un caso base, la recursividad no terminará.
2. Asegúrate de que el problema se reduce: Cada llamada recursiva debe acercarse al caso base.
3. Evita la recursividad innecesaria: Si un problema puede resolverse fácilmente con iteración, usa iteración.
4. Prueba con casos pequeños: Verifica tu método con entradas pequeñas para asegurarte de que funciona.

¡Cuidado con la recursividad!

• Stack Overflow (desbordamiento de la pila de ejecución): Si la recursividad se ejecuta sin un caso base adecuado, puede llevar a un error de Stack Overflow, ya que la pila de llamadas se llena demasiado.
• Eficiencia: Cuando un problema puede resolverse de forma iterativa, los bucles iterativos suelen ser más eficientes. La recursividad puede ser menos eficiente en términos de memoria y tiempo, ya que cada llamada recursiva consume espacio en la pila de ejecución.

Recuerda:

• La recursividad puede ser más legible y fácil de entender en algunos casos, pero no siempre es la solución más eficiente.
• La recursividad implica que una función se llama a sí misma dentro de su propia definición.
• Un caso base es esencial para detener la recursión y evitar errores de Stack Overflow.

Ejercicios propuestos

1. Escribe un método recursivo para calcular la suma de los primeros n números naturales.
2. Implementa un método recursivo para calcular la potencia de un número aa elevado a bb.
3. Crea un método recursivo para invertir una cadena de texto.