Fibonacci recursivo en C++

1. Funciones recursivas en C++
2. Tipos de recursividad
3. Serie de Fibonacci
4. Serie de Fibonacci en C++

Este pequeño tutorial explicará cómo implementar la serie de Fibonacci usando la función recursiva en C++. Para eso, primero tendremos una breve introducción sobre las funciones recursivas.

Funciones recursivas en C++

Una función recursiva se invoca a sí misma dentro de su propio cuerpo, y usar este concepto se llama recursividad. Este concepto es útil de muchas maneras, y algunas funciones se pueden implementar usando solo recursividad.

La figura anterior muestra el concepto de recursividad. En la función main, se llama a una función recurse, y en esa función, se vuelve a llamar a recurse.

Esto creará una llamada recursiva y el programa continuará sus iteraciones en esta función hasta que se cumpla alguna condición. Usualmente, la estructura if...else se usa en las funciones recursivas, con una ruta haciendo una llamada recursiva y la otra saliendo de la función; De lo contrario, se producirá una recursividad infinita.

La recursividad realiza varias llamadas repetidas a la función desde dentro de la función. La condición recursiva invoca la función nuevamente hasta que se satisface el caso base.

El caso base está contenido dentro de la función y finaliza la ejecución cada vez que se cumple la condición del caso base.

Código:

void recursiveFun(int x) {
  if (x == 0) return;
  x = x - 1;
  recursiveFun(x);
}

La función anterior, una vez llamada con el argumento x, se llamará recursivamente a sí misma con un valor reducido de x (es decir, [x-1, x-2,…, x-(x-1)]) hasta que x se convierte en cero. Cuando se encuentra x con valor cero, el programa deja de generar nuevas llamadas recursivas y comienza a devolver valores (si los hay) de abajo hacia arriba.

Aunque la recursividad se puede utilizar para resolver casi todos los problemas, hay instancias selectivas en las que es realmente beneficiosa. Se usa comúnmente para manejar asuntos difíciles y problemas que siguen un patrón jerárquico; aborda el problema principal resolviendo subproblemas más pequeños.

Tipos de recursividad

La recursividad directa y la recursividad indirecta son los dos tipos de recursividad.

recursividad directa

La función recursiva se llama a sí misma directamente en su propio cuerpo a través de la recursividad directa.

void recursion() { ....recursion(); }

En el código, podemos ver que la función se llama a sí misma en su propio cuerpo o paréntesis.

recursividad indirecta

En la recursividad indirecta, la función se llama indirectamente en el cuerpo de cualquier otra función.

void func1() { ... func2(); }
void func2() { ... func1(); }

Serie de Fibonacci

La serie de Fibonacci es un conjunto de números enteros en el que cada número sucesivo es la suma de los dos anteriores. Los dos primeros números, 0 y 1, y el tercero se calculan sumando los dos primeros.

La fórmula para calcular la serie de Fibonacci es:

Por ejemplo 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Podemos ver que el tercer elemento, 1, es la suma de 0+1. Del mismo modo, el cuarto número, 2, es la suma de los números anteriores (1+1=2).

Por tanto, podemos predecir que el siguiente elemento de la serie será 21+34 = 55.

Serie de Fibonacci en C++

Para implementar la serie de Fibonacci, podemos implementar una función recursiva que puede tomar como entrada un número e imprimirá la serie de Fibonacci de esa cantidad. Por ejemplo, si el usuario ingresa 8, imprimiremos 8 números de la serie.

Código:

#include <iostream>
using namespace std;

int fibonacci(int num) {
  if (num <= 1) return num;
  return fibonacci(num - 1) + fibonacci(num - 2);
}

int main() {
  int num;
  cout << "Enter a number: ";
  cin >> num;
  for (int a = 0; a < num; a++) {
    cout << fibonacci(a) << " ";
  }
  return 0;
}

En la función principal, solicitamos al usuario que ingrese un número. Después de eso, iteramos un bucle desde 0 hasta ese número de entrada num y pasamos la variable iteradora a a la función Fibonacci.

Este ciclo iterará num veces el número ingresado por el usuario. En la función Fibonacci, tenemos una condición if que verificará si el número es menor que 1, luego devolverá ese número.

De lo contrario, llamará a la función fibonacci para num-1 y num-2 porque cada siguiente número de la serie se calcula sumando los dos números anteriores, es decir, n-1 y n-2.

Producción:

El usuario ha introducido el número 9, por lo que se ha impreso la serie de Fibonacci con 9 valores.