fibonacci se define como
f(0)=0;
f(1)=1;
f(n)=f(n-1)+f(n-2);
la misma definicion te dice como implementar una funcion que calcule fibonnacci:
int fibo (int n)
{
if (n>1) return f(n-1)+f(n-2); // Si n > 1 usas f(n)=f(n-1)+f(n-2);
return n; // si n es 0 o 1 devolves su valor. usas f(0)=0; o f(1)=1;
}
Existen muchas consideraciones adicionales a tener en cuenta. por ejemplo en el caso de fibonnacci de 5estas calculando f(3) mas de una vez. imaginate si haces fibo de 256 calculas muchas veces lo mismo. por lo tanto podrias mantener en un arreglo los valores ya calculados y asi mejorar la eficiencia de tu programa.
por ejemplo, la siguiente funcion es mas eficiente que la anterior:
int fiboEficiente (int n, Dictionary<int,int> valoresYaCalculados)
{
if (valoresYaCalculados.ContainsKey(n)) // si el valor ya lo calculastes => devolves el valor
{
return valoresYaCalculados[n];
}
// Calculo por primera y unica vez el fibo n usando la primera
int fiboN = fiboEficiente (n-1,valoresYaCalculados) + fiboEficiente (n-2,valoresYaCalculados);
valoresYaCalculados.Add(n,fiboN ); // Agrego el resultado de fibo de n para no volver a calcularlo
return fiboN; // retorno el fibo de n
}
una invocacion a la segunda funcion seria:
Dictionary<int,int> valoresCalculados = new Dictionary<int,int>();
int fiboN = fiboEficiente (n, valoresCalculados);
esta funcion ademas te permite tambien obtener todos los valores de fibonacci desde 2..n en el dictionary valoresCalculados.
bueno espero sea de ayuda. cualquier duda pregunta nomas.
saludos, daniel.
Referencias:
funciones recursivas.
sucesion de fibonacci
diccionarios
programacion dinamica
