0,1,1,2,3,5,8,13,21,. . .

 Observando con atención la secuencia de números anteriores, podremos caer en la cuenta de que todos sus términos, menos el primero y el segundo, se obtienen sumando los dos anteriores. De esta forma, tenemos que: 2 = 1 + 1; 3 = 1 + 2; 5 = 2 + 3; 8 = 3 + 5; y, así, hasta “el infinito y más allá”.

En un sentido amplio, el término general de una sucesión no es más que la expresión matemática de la regla de formación. Siguiendo este enfoque, podemos representar, sin problemas, el término general de la sucesión de Fibonacci de forma recurrente.

Puede ser definida en forma recursiva por:

Solución iterativa

int fibonacci (int n)
{
  int actual, ant1, ant2; ant1 = ant2 = 1;
  if ((n == 0) || (n == 1)) 
    { actual = 1;
    } else
         {  for (i=2; i<=n; i++) 
              { actual = ant1 + ant2; ant2 = ant1;
                ant1 = actual;
              }
         }
 return (actual);
}

 El programa respectivo en versión recursiva seria:

long flbonacci (int n)
 		{
 
                 if (n==0 jj n==1) 
                    return n;
                 else return flbonacci(n-1)+flbonacci(n-2);
 
                }

Cada vez que se invoca a flbonacci se prueba el caso base, es decir si n es 0 o 1. Si esto es verdadero se regresa n. Si n es mayor que 1 el paso de recursión genera dos llamadas recursivas cada una de las cuales es para un problema ligeramente más sencillo que el original (valores de n menores).

---