Recursividad en programación C++

Recursividad en programación C++

El proceso de llamar a una función por sí misma se llama recursividad. La recursividad se usa con frecuencia en matemáticas para resolver un problema complejo dividiéndolo en un problema más simple del mismo tipo. De manera similar, en la programación, se puede usar para dividir un problema más grande en muchos problemas más simples y resolverlos individualmente. El formato general de una función recursiva es:

returntype recursive_func ([argument list])
{
    statements;
    ... ... ...
    recursive_func ([actual argument])
    ... ... ...
}

Diagrama de flujo para recursividad

Mientras usamos la recursividad, necesitamos definir una condición de salida adecuada para evitar llamadas recursivas infinitas. La recursividad usa una pila para guardar el contenido de la función actual antes de realizar una llamada recursiva.

Tipos de recursividad

  • Recursión directa
  • Recursión indirecta

Recursión directa

Una función cuando se llama a sí misma directamente se conoce como recursividad directa.

Por ejemplo ,

int factorial (int n)
{
    if (n==1 || n==0)
        return 1;
    else
        return n*factorial(n-1);
}

Aquí, dentro de factorial(int n) , directamente se llama a sí mismo como n*factorial(n-1) . Esto es recursividad directa.

Recursión indirecta

Se dice que una función es recursiva indirecta si llama a otra función y la nueva función vuelve a llamar a la primera función que llamó.

Por ejemplo ,

int func1(int n)
{
    if (n<=1)
        return 1;
    else
        return func2(n);
}

int func2(int n)
{
    return func1(n-1);
}

Aquí, la recursión tiene lugar en 2 pasos, a diferencia de la recursión directa.

  • Primero, func1 llama a func2
  • Entonces, func2 devuelve la llamada a la primera función de llamada func1.

Ejemplo n.° 1:el programa C++ imprime los primeros n números de Fibonacci usando la recursividad.

#include<iostream>
using namespace std;

int fibo(int num)
{
    if(num==1||num==2)
        return 1;
    else
        return (fibo(num-1)+fibo(num-2));  // recursive call
}

int main()
{
    int i,n;
    cout<<"Enter the required term: ";
    cin>>n;
    cout<<"First "<<n<<" fibonacci numbers are"<<endl;
    for (i=1; i<=n; i++)
        cout<<fibo(i)<<endl;
    return 0;
}

En este programa, se utiliza el concepto de recursividad para generar series de Fibonacci ya que un término se representa como la suma de dos términos más pequeños. Serie de Fibonacci es una serie donde se genera un término sumando dos términos anteriores de esa serie. Matemáticamente ,

tn = tn-1 + tn-2

Aquí,

  • La cantidad de términos de Fibonacci que se generarán se toma del usuario y se almacena en la variable n.
  • Un bucle for se usa para recorrer el número que se generará y se envía a la función fibo . Esta función se utiliza para calcular y devolver series de Fibonacci.
  • Dentro de fibo , si el número de término es 1 o 2, devuelve 1. Esto se debe a que los dos primeros términos de la serie de Fibonacci son ambos 1. Los valores impresos son 1,1 .
  • Luego el siguiente término-número 3 se pasa a fibo función, dado que no es 1 ni 2, el siguiente término de la serie se calcula tomando fibo(n – 1) + fibo(n – 2) , donde n =3 . Esto calcula los dos últimos términos de la serie de Fibonacci. Esto es equivalente a fibo(2) + fibo(1) , lo que da como resultado 1 + 1 =2 .
  • Este bucle recursivo finalmente imprime la serie como 1, 1, 2, 3, 5...

Salida

Enter the required term: 7
First 7 fibonacci numbers are
1
1
2
3
5
8
13

Desventajas de la recursividad

  • Los programas recursivos son generalmente más lentos que los programas no recursivos. Esto se debe a que la función recursiva necesita almacenar las direcciones de llamada de función anteriores para que se produzca el salto de programa correcto.
  • Requiere más memoria para contener estados intermedios. Esto se debe a que el programa recursivo requiere la asignación de un nuevo marco de pila y cada estado debe colocarse en el marco de pila, a diferencia de los programas no recursivos (iterativos).