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.

En general, 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.

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 (s 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.

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 overflow 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.

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