Recursividad

¿Qué es la recursividad?

La recursividad es una técnica de programación en la que una función se llama a sí misma para resolver un problema. En lugar de utilizar bucles o iteraciones, la recursividad permite que una función se divida en subproblemas más pequeños y manejables, lo que puede simplificar el código y hacerlo más fácil de entender.

Cómo funciona la recursividad

Una función recursiva generalmente consta de dos partes:

1. Caso base: Es la condición que detiene la recursión. Sin un caso base, la función se llamaría a sí misma indefinidamente, lo que resultaría en un error de desbordamiento de pila.
2. Caso recursivo: Es la parte de la función que se llama a sí misma con un conjunto de parámetros modificados, acercándose al caso base.

Preguntas para saber si un problema es adecuado para la recursividad

1. ¿El problema se puede dividir en subproblemas más pequeños del mismo tipo?
2. ¿Existe un caso base que detenga la recursión?
3. ¿La solución recursiva es más fácil de entender o implementar que una solución iterativa?

Si logras responder "sí" a estas preguntas, es probable que la recursividad sea una buena opción para resolver el problema.

Ejemplo de recursividad: Factorial

El factorial de un número entero positivo n se define como el producto de todos los enteros desde 1 hasta n. La función factorial se puede implementar de manera recursiva de la siguiente manera:

public int factorial(int n) {
    // Caso base: el factorial de 0 es 1
    if (n == 0) {
        return 1;
    }
    // Caso recursivo: n! = n * (n - 1)!
    return n * factorial(n - 1);
}

En este ejemplo, el caso base es cuando n es igual a 0, donde el factorial de 0 es 1. El caso recursivo se define como n! = n * (n - 1)!, lo que significa que la función se llama a sí misma con n - 1 hasta llegar al caso base.

Ejemplo de recursividad: Fibonacci

La secuencia de Fibonacci es una serie de números donde cada número es la suma de los dos anteriores. La función para calcular el n-ésimo número de Fibonacci se puede implementar de manera recursiva de la siguiente manera:

public int fibonacci(int n) {
    // Casos base: F(0) = 0, F(1) = 1
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    }
    // Caso recursivo: F(n) = F(n - 1) + F(n - 2)
    return fibonacci(n - 1) + fibonacci(n - 2);
}

En este ejemplo, los casos base son cuando n es igual a 0 o 1, donde el número de Fibonacci es 0 y 1 respectivamente. El caso recursivo se define como F(n) = F(n - 1) + F(n - 2), lo que significa que la función se llama a sí misma con n - 1 y n - 2 hasta llegar a los casos base.

Conclusión

La recursividad es una técnica poderosa en programación que permite resolver problemas de manera elegante y eficiente. Al comprender cómo funciona la recursividad y cuándo es apropiada, puedes escribir código más limpio y fácil de entender. Sin embargo, es importante tener cuidado al usar la recursividad, ya que un caso base mal definido o una recursión infinita pueden llevar a errores de desbordamiento de pila.