11. Recursividad

La recursividad en programación ocurre cuando una función se llama a sí misma para resolver un problema en partes más pequeñas hasta alcanzar un punto final.

Ejemplo clásico: Factorial recursivo


Veamos primero una función recursiva sencilla para calcular el factorial de un número:
Concepto matemático:   n!=n×(n−1)!n!=n×(n−1)!

Implementación en C++:

#include <iostream>

using namespace std;

int factorial(int n);// Prototipo Función factorial recursiva

}

int main() {
    int numero = 5;
    cout << "El factorial de " << numero << " es: " << factorial(numero);
    return 0;
}

//Declaración de la función de Factorial

int factorial(int n) {
    // Caso base
    if (n <= 1) {
        return 1;//Punto final!!
    }
    // Caso recursivo
    else {
        return n * factorial(n - 1);
    }


Otro ejemplo: Serie Fibonacci

Recordando, la serie de Fibonacci tenía la siguiente ley: 0, 1, 1, 2, 3, 5, 8, ...

Semillas (dos primeros términos 0 y 1), luego el termino n para n>=3 se logra sumado, es decir x3=x2+x1 o en general xn=xn-1+xn-2  en otras palabras obtengo un termino sumando los dos anteriores.

Implementación en C++:

#include <iostream>

using namespace std;

int fibonacci(int n);//Prototipo

int main() {
    int num = 6;//Calcula los terminos de fibo hasta num
    cout << "El fibonacci de " << num << " es: " << fibonacci(num);
    return 0;
}

//Declaración de la función de Fibonacci
int fibonacci(int n) {
    // Casos base
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    // Caso recursivo
    return fibonacci(n - 1) + fibonacci(n - 2);
}

✅ Ventajas

  • Código más claro y elegante para ciertos problemas.

  • Fácil de implementar y entender en problemas pequeños.

❌ Desventajas

  • Puede consumir más memoria debido a múltiples llamadas.

  • Más lento en ciertos problemas comparado con iteración.

  • Riesgo de desbordamiento de pila (Stack Overflow).


Otro ejemplo: Convertir un decimal a binario


Implementación en C++:

#include <iostream>

using namespace std;
void decimalABinario(int numero);//Prototipo

int main() {
    int numero = 13;
    cout << "El número " << numero << " en binario es: ";
    decimalABinario(numero);
    return 0;
}

// Declaración de la Función recursiva
void decimalABinario(int numero) {
    if (numero < 2) { // Caso base
        cout << numero;
        return;
    }
    decimalABinario(numero / 2); // Caso recursivo
    cout << numero % 2; // imprime el resto después de la llamada recursiva
}