Recursividad cpp

Recursividad

#include <iostream>

using namespace std;

long fibonacci(long x);

int main(){
    long a;
    cout << "Ingresa cantidad de numeros" << '\n';
    cin >> a;
    cout << fibonacci(a) << endl;
}

long fibonacci(long x){
    if(x <= 1)
        return x;
    return fibonacci(x - 1) + fibonacci(x - 2);
}

Un tema interesante dentro de funciones son las funciones recursivas, es decir funciones que se contienen o se llaman a si mismas, ejemplos de este tipo de problemas son la sucesión de fibonacci y la función factorial.

Otra forma de ver la recursividad es como un ciclo, ya que la función se llama varias veces hasta que llega al resultado esperado.

Recursividad vs iterativo

Aunque en ejecución podrian verse iguales, en términos de costo de memoria no lo son, el iterativo en principio puede parecer menos costoso pero eso solo depende de la cantidad de ciclos anidados que tenga, llegando a tener un gran costo de ejecución.

La recursividad en cambio cada llama a otra función hace uso de memoria, y se va acumulando en el stack de memoria.

Aunque la recursividad suena interesante y suele proveer soluciones mas elegantes que las iterativas, no siempre es recomendable, ya que en el peor de los casos podríamos quedarnos sin memoria, se recomienda usarla cuando sabemos que se tendrán pocas iteraciones o cuando la solución recursiva es la única alternativa.

Sucesión de fibonacci

Tenemos la sucesión de fibonacci $0,1,1,2,3,5,8,13,21,34,...,$, sabemos que empieza en 0, por lo que nos interesa llegar a este resultado, por lo que podemos partir de su definición

$$\begin{matrix} f_0 = 0 \\ f_1 = 1 \\ f_{n} = f_{n-1}+f{n-2} \end{matrix} $$

También podemos tomar $f_1 = 1$ en vez de 0, así cuando el valor mandado a la función valga 0 o 1, dejaremos de llamar a la función.

long fibonacci(long x){
    if(x <= 1)
        return x;
    return fibonacci(x - 1) + fibonacci(x - 2);
}   

Esto hará que se ejecuten todas las llamadas al stack.

Introducción	Funciones	Funciones anónimas	Macros