Qué es y cómo usar las funciones recursivas

La recursividad es un concepto en programación en el que una función se llama a sí misma para resolver un problema.

La recursividad siempre es algo problemática y difícil de entender. Sobre todo, para los que están empezando en la programación.

Sin embargo, algunos problemas son más sencillos de resolver aplicando recursividad. No todos, ni mucho menos. Más bien una parte pequeña de los problemas.

Funcionamiento de la Recursividad

En realidad la recursividad es fácil de implementar. Simplemente tenemos una función que, en algún momento, se invoca a si misma.

Esta estructura es bastante parecida a un bucle, en cuanto a que es un fragmento de código que se ejecuta varias veces. Sin embargo, no es exactamente igual. Cada llamada a la función genera su propio marco, donde se almacenan las variables locales.

Por otro lado, de igual forma que en un bucle tenemos el riesgo de tener un bucle infinito, una función recursiva puede caer en un bucle sin fin.

Es decir ¿Cuándo se para esta serie de llamadas? En algún momento, la función tiene que hacer “algo” que no sea llamarse a si misma. A estos casos los llamaremos caso base.

A medida que se alcanza el caso base y se resuelven los subproblemas, las llamadas recursivas regresan, liberando los marcos de pila y permitiendo que la función original complete su tarea.

Cómo detectar soluciones recursivas

¿Cómo podemos detectar soluciones que podrían resolverse de forma más fácil con una aproximación recursiva?

Cuando tengamos un problema que tiene varios pasos, y el resultado de ejecutar cada paso nos deja un problema igual al anterior.

Ejemplo, supongamos que tenemos una bandeja con 5 pasteles, y 5 comensales. Tenemos darle un pastel a cada comensal.

Cogemos el primer pastel, y hacemos lo que haya que hacer. Decidimos por si uno tiene más hambre que otro, si es intolerante a algo, si le gusta el chocolate o la nata. Da igual, la cosa es que asignamos un pastel.

Ahora tenemos un pastel asignado, y el problema que nos queda es el mismo. Pero ahora tenemos un 4 pasteles y 4 comensales. Es un ejemplo muy tonto, pero sirve para explicar la recursividad.

En cada paso, el nuevo problema que nos queda es idéntico al anterior, pero con menos elementos. Esto nos indica que una aproximación recursiva podría ser más sencilla.

Ejemplos de funciones recursivas en distintos lenguajes

Vamos a ver ejemplos de funciones recursivas en distintos lenguajes. Para ello vamos a usar un ejemplo muy sencillo, el cálculo del factorial de un número.

No es el caso más interesante del mundo, ni el más práctico. Pero viene muy bien porque es muy sencillo.

Podemos identificar que es un problema susceptible de ser resuelto por una aproximación recursiva porque, en cada paso, “lo que nos queda por calcular” es idéntico a “lo que ya hemos calculado”.

Es decir,

Y así sucesivamente hasta llegar a 1.

Vamos a ver como resolveríamos este problema de forma recursiva en distintos lenguajes.

#include <iostream>

// Función recursiva para calcular el factorial de un número
int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1; // Caso base: factorial de 0 y 1 es 1
    } else {
        return n * factorial(n - 1); // Llamada recursiva
    }
}

int main() {
    int num = 5;
    int resultado = factorial(num);
    std::cout << "El factorial de " << num << " es: " << resultado << std::endl;
    return 0;
}

using System;

public class Program {
    // Función recursiva para calcular el factorial de un número
    public static int Factorial(int n) {
        if (n == 0 || n == 1) {
            return 1; // Caso base: factorial de 0 y 1 es 1
        } else {
            return n * Factorial(n - 1); // Llamada recursiva
        }
    }

    public static void Main() {
        int num = 5;
        int resultado = Factorial(num);
        Console.WriteLine("El factorial de " + num + " es: " + resultado);
    }
}

// Función recursiva para calcular el factorial de un número
function factorial(n) {
    if (n === 0 || n === 1) {
        return 1; // Caso base: factorial de 0 y 1 es 1
    } else {
        return n * factorial(n - 1); // Llamada recursiva
    }
}

let num = 5;
let resultado = factorial(num);
console.log(`El factorial de ${num} es: ${resultado}`);

# Función recursiva para calcular el factorial de un número
def factorial(n):
    if n == 0 or n == 1:
        return 1  # Caso base: factorial de 0 y 1 es 1
    else:
        return n * factorial(n - 1)  # Llamada recursiva

num = 5
resultado = factorial(num)
print(f"El factorial de {num} es: {resultado}")

Stack overfow y casos base

Hemos dicho que uno de los problemas de las funciones recursivas es saber cuando tienen que parar. A esto le llamamos los casos base.

Si no paramos las llamadas recursivas, nos metemos en un bucle infinito. Cada llamada recursiva agrega un marco de pila a la memoria y si estos marcos de pila se acumulan sin liberarse, se produce el desbordamiento.

El desbordamiento de la pila (stack overflow) ocurre cuando una función recursiva se llama a sí misma demasiadas veces, y el tamaño de la pila de llamadas supera el límite establecido.

Veamos un ejemplo que generaría un Stack Overflow.

// Función recursiva con riesgo de Stack Overflow
int funcionRecursivaConStackOverflow(int n) {
    return funcionRecursivaConStackOverflow(n + 1); // Llamada recursiva sin caso base
}

int main() {
    int num = 0;
    int resultado = funcionRecursivaConStackOverflow(num);
    std::cout << "Resultado: " << resultado << std::endl; // Nunca se llegará aquí
    return 0;
}

En el ejemplo anterior, la función funcionRecursivaConStackOverflow se llama a sí misma sin un caso base, lo que provocará un desbordamiento de la pila y un cierre abrupto del programa.

Por tanto, necesitamos uno o varios casos base, que detengan el proceso de llamadas recursivas.

int funcionRecursivaConStackOverflow(int n) {
	if(n > 10) return 10; // caso base si n > 10
    return funcionRecursivaConStackOverflow(n + 1);
}

int main() {
    int num = 0;
    int resultado = funcionRecursivaConStackOverflow(num);
    std::cout << "Resultado: " << resultado << std::endl; // muestra 10
    return 0;
}

En este caso, hemos metido un condicional que detiene las llamadas recursivas. Si n > 10 no se realiza la llamada recursiva.

En el ejemplo, el resultado de toda la serie de llamadas sería mostrar por pantalla 10. Acabamos de hacer un contador hasta 10 innecesariamente complicado. Pero para el ejemplo, nos vale 😉.

Lo importante es entender que una función recursiva tiene que tener algún tipo de condición en el que no se llama a si misma. O, tendréis un bucle sin fin y un desbordamiento de pila.

Equivalencia lógica recursividad - iterativa

Cualquier función recursiva puede convertirse en una función no recursiva utilizando un enfoque iterativo. Esto a menudo mejora el rendimiento y evita el riesgo de desbordamiento de la pila (stack overflow).

Por ejemplo, el cálculo del factorial en su versión recursiva

// Función recursiva para calcular el factorial de un número
int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1; // Caso base: factorial de 0 y 1 es 1
    } else {
        return n * factorial(n - 1); // Llamada recursiva
    }
}

int main() {
    int num = 5;
    int resultado = factorial(num);
    std::cout << "El factorial de " << num << " es: " << resultado << std::endl;
    return 0;
}

Puede pasarse a una versión iterativa, por ejemplo de la siguiente forma,

// Versión no recursiva (iterativa) para calcular el factorial de un número
int factorialNoRecursivo(int n) {
    int resultado = 1;
    for (int i = 1; i <= n; i++) {
        resultado *= i;
    }
    return resultado;
}

int main() {
    int num = 5;
    int resultado = factorialNoRecursivo(num);
    std::cout << "El factorial de " << num << " es: " << resultado << std::endl;
    return 0;
}

En este ejemplo, hemos reemplazado la función recursiva del cálculo del factorial con una versión no recursiva que utiliza un bucle for para calcular el resultado de manera iterativa.

Ventajas y desventajas de la recursividad

Ventajas de la recursividad

• Facilidad: En algunos casos determinados, implementar una solución recursiva puede ser más sencillo que una solución iterativa

• División de Problemas: La recursividad nos permite dividir un problema complejo en subproblemas más simples y resolver cada subproblema de forma recursiva.

• Eficiencia para Estructuras Jerárquicas: En problemas que involucran estructuras jerárquicas, como árboles o grafos, la recursividad puede ser una forma natural y eficiente de recorrer y manipular estos elementos.

Desventajas de la recursividad

• Lógica Compleja: Algunos problemas pueden tener soluciones recursivas complejas, lo que puede dificultar su implementación y comprensión para programadores menos experimentados.

• Mayor consumo de memoria: Cada llamada recursiva crea un nuevo marco de pila, lo que puede llevar al desbordamiento de la pila (stack overflow) si el número de llamadas recursivas es muy grande. Esto puede hacer que las soluciones recursivas sean menos eficientes en términos de consumo de memoria en comparación con enfoques iterativos.

• Menor eficiencia: En algunos casos, las soluciones recursivas pueden requerir más tiempo de ejecución en comparación con enfoques iterativos.

• Dificultad de depuración: La recursividad puede dificultar la depuración y el seguimiento de errores, especialmente cuando hay múltiples llamadas recursivas y la profundidad de la recursión es alta.