Conceptos Clave en Recursividad

Caso Base

El caso base es la condición que termina la recursión. Define el resultado para los casos más simples y evita que la función se llame a sí misma indefinidamente. Sin un caso base adecuado, la función recursiva puede provocar un desbordamiento de pila debido a llamadas infinitas.

  • Propósito: Evitar la recursión infinita y proporcionar un resultado inmediato para casos triviales o simples.
  • Ejemplo: En la función para calcular el factorial, factorial(0) = 1 es el caso base porque 0! siempre es 1.

Caso General

El caso general es la parte de la función que llama a sí misma con argumentos modificados. Descompone el problema en subproblemas más pequeños y más manejables, que eventualmente llegarán al caso base.

  • Propósito: Dividir el problema en subproblemas más simples y usar la recursión para resolverlos.
  • Ejemplo: En la función para calcular el factorial, el caso general es factorial(n) = n * factorial(n-1).

Ejercicio: Serie Fibonacci con Recursividad

La serie de Fibonacci es una secuencia de números en la que cada número es la suma de los dos números anteriores. La serie empieza con 0 y 1. La fórmula recursiva para la serie de Fibonacci es:

  • fibonacci(n) = n si n < 2 (caso base)
  • fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) si n >= 2 (caso general)

Código en C++

/* Ejercicio 20: Realice una función recursiva para la serie Fibonacci  
Nota: La serie de Fibonacci está formada por la secuencia de números:  
0, 1, 1, 2, 3, 5, 8, 13, 21, 34...  

fibonacci(n) = n                              , si n < 2
               fibonacci(n-1) + fibonacci(n-2), si n >= 2
*/

#include <iostream>
#include <stdlib.h>
using namespace std;

int fibonacci(int n);

int main() {
    int nElementos;

    // Pedimos un numero entero positivo
    do {
        cout << "Digite el numero de elementos: ";
        cin >> nElementos;
    } while (nElementos <= 0);

    // Mandamos llamar a la funcion pero de forma iterativa para imprimir todos los elementos
    cout << "Serie Fibonacci: ";
    for (int i = 0; i < nElementos; i++) {
        cout << fibonacci(i) << " , ";    
    }

    cout << "\n";
    system("pause");
    return 0;
}

// Función recursiva para calcular el n-ésimo número de la serie Fibonacci
int fibonacci(int n) {
    if (n < 2) { // Caso base
        return n;
    } else { // Caso general
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

Explicación del Código

  1. Caso Base:
   if (n < 2) {
       return n;
   }
  • Este caso maneja los números 0 y 1, que son los dos primeros números de la serie de Fibonacci. Para estos valores, el resultado es simplemente n porque fibonacci(0) = 0 y fibonacci(1) = 1.
  1. Caso General:
   return fibonacci(n-1) + fibonacci(n-2);
  • Para valores de n mayores o iguales a 2, la función se llama a sí misma con n-1 y n-2, sumando los resultados para obtener el número de Fibonacci en la posición n.
  1. Función Principal (main):
   int main() {
       int nElementos;

       do {
           cout << "Digite el numero de elementos: ";
           cin >> nElementos;
       } while (nElementos <= 0);

       cout << "Serie Fibonacci: ";
       for (int i = 0; i < nElementos; i++) {
           cout << fibonacci(i) << " , ";    
       }

       cout << "\n";
       system("pause");
       return 0;
   }
  • Se solicita al usuario el número de elementos para la serie Fibonacci y luego se imprime la serie usando un bucle que llama a la función recursiva fibonacci.

Resultado de Ejecución

Digite el numero de elementos: 5
Serie Fibonacci: 0 , 1 , 1 , 2 , 3 ,
Presione una tecla para continuar . . .

Consideraciones

  • Eficiencia: La solución recursiva para la serie de Fibonacci puede ser ineficiente para valores grandes de n debido a la recomputación repetida de valores. Para mejorar la eficiencia, se pueden usar técnicas como la memorización o la iteración.
  • Entendimiento: Es importante identificar claramente el caso base y el caso general para evitar errores en la función recursiva.

La recursividad proporciona una manera elegante de resolver problemas que pueden ser descompuestos en subproblemas similares, como la serie de Fibonacci. Sin embargo, es crucial gestionar correctamente el caso base y el caso general para asegurar la correcta ejecución y eficiencia del programa.