Problema Fibonacci P1

Descripción:

Diseña un programa recursivo final que calcule el nésimoelemento de la sucesión de Fibonacci.

• Según se ha visto, la técnica consiste en usar parámetros acumuladores, en el presente problema necesitamos dos: uno que almacene fib(n-2) (lo llamaremos f0), y otro que almacene fib(n-1) (lo llamaremos f1).
• La función principal llamará a una auxiliar dándole valores iniciales a los acumuladores. También usaremos un parámetro i, que se incrementará en cada llamada.
• El caso base: i = n, devolveremos el acumulador que contenga f1 + f0
• Caso recursivo: con cada acumulador ocurrirá la transformación esperada al pasar de n a n+1
• Diseña un programa iterativo que calcule el n-ésimo elemento de la sucesión de Fibonacci, transformando el recursivo final del ejercicio anterior.
• Para resolver este ejercicio nos basaremos en una transparencia anterior donde se mostraba la transformación a iterativo del factorial recursivo final.
  

Solución:

private static long fibRec0(long n) {
long r;

if (n <= 1) {
r = n;
} else {
r = fibRec0(n - 1) + fibRec0(n - 2);
}
return r;
}

private static long fibFinal(long n) {
long res = 0;
if (n < 2) {
// TODO
res=n;
} else {
// TODO
res=fibFinalAux(n,1,0,1);
}
return res;
}

private static long fibFinalAux(long n, long i, long f0, long f1) {
long res = 0;

if (i == n) {
// TODO
res=f1;
} else {
// TODO
res=fibFinalAux(n,i+1,f1,f0+f1);
}
return res;
}

private static long fibIter(long n) {
long f0 = 0;
long f1 = 1;
long i = 1;
long faux = 0;
long res = 0;

if (n < 2) {
// TODO
res=n;
} else {
while (i < n) {
// TODO
faux=f1;
f1+=f0;
f0=faux;
i++;
}
// TODO
res=f1;
}
return res;
}
}