Concepto de Recursividad

Una función es recursiva si realiza al menos una llamada a sí misma dentro de su definición. Para que una función recursiva funcione correctamente, debe tener dos componentes clave:

  1. Caso Base: Una condición que detiene las llamadas recursivas y evita la llamada infinita, proporcionando una solución directa y simple para el problema en su forma más sencilla.
  2. Caso Recursivo: La parte de la función que se llama a sí misma con un argumento modificado para acercarse al caso base.

La estructura general de una función recursiva se puede describir como sigue:

tipoDeRetorno nombreFuncion(parametros) {
    if (condiciónBase) {
        // Caso base: retorna un valor específico
    } else {
        // Caso recursivo: llamada a sí misma con parámetros modificados
        return nombreFuncion(parametrosModificados);
    }
}

Ejemplo en C++: Factorial de un Número

El factorial de un número n, denotado como n!, es el producto de todos los números enteros positivos menores o iguales a n. Se define de la siguiente manera:

  • 0! = 1 (Caso base)
  • n! = n * (n-1)! para n > 0 (Caso recursivo)

Código:

/* Recursividad

Factorial de un número:
3! = 3 * 2 * 1 = 3 * 2!
0! = 1

Definición recursiva:
factorial(n) = 1        , si n = 0
               n * factorial(n-1)   , si n > 0
*/

#include <iostream>
#include <stdlib.h>

using namespace std;

// Prototipo de función
int factorial(int);

// Función principal
int main() {
    int num = 5; // Número del cual se calculará el factorial
    cout << "El factorial de " << num << " es: " << factorial(num) << endl;
    system("pause"); // Pausar la ejecución para ver el resultado
    return 0;
}

// Función para calcular el factorial de un número de manera recursiva
int factorial(int n) {
    if (n == 0) { // Caso base
        return 1; // 0! = 1
    } else { // Caso recursivo
        return n * factorial(n - 1); // n! = n * (n-1)!
    }
}

Explicación del Código

  1. Definición del Caso Base:
   if (n == 0) {
       return 1;
   }
  • El caso base se activa cuando n es igual a 0. En este caso, el factorial de 0 es 1, que es el resultado base para la recursión.
  1. Definición del Caso Recursivo:
   return n * factorial(n - 1);
  • El caso recursivo multiplica n por el factorial de n - 1. La función se llama a sí misma con n - 1, acercándose al caso base.
  1. Función Principal (main):
   int main() {
       int num = 5;
       cout << "El factorial de " << num << " es: " << factorial(num) << endl;
       system("pause");
       return 0;
   }
  • Llama a la función factorial con el número 5 y muestra el resultado. system("pause") se utiliza para pausar la ejecución y permitir al usuario ver el resultado en la consola.

Resultado de Ejecución

El factorial de 5 es: 120
Presione una tecla para continuar . . .

Consideraciones

  • Eficiencia: Las llamadas recursivas pueden consumir más memoria debido a la pila de llamadas. Para números grandes, se pueden considerar alternativas como la iteración para evitar problemas de desbordamiento de pila.
  • Entendimiento: Es crucial entender el caso base y el caso recursivo para evitar llamadas infinitas y asegurar que la función recursiva termine correctamente.

La recursividad es una herramienta poderosa para resolver problemas que pueden dividirse en subproblemas similares. En el caso del factorial, la técnica recursiva simplifica la solución al descomponer el problema en casos más manejables.