Ahora que he tenido un poco más de tiempo, aquí tienes mi propuesta usando recursividad y memoización.
Como siempre, en los comentarios tienes explicaciones de todo y para cualquier duda, no dudes en preguntar
// Primero que nada, declaramos un array donde almacenaremos los números
public static int[] calculatedNumbers;
public static void main(String[] args) {
int n = 43;
/* A continuación, instanciamos el array con la longitud máxima igual al número que vamos a calcular
* +1, así evitamos salirnos de índice al acceder a calculatedNumbers[n] y además no tenemos que
* poner -1 cada vez que queramos usar el índice.
*/
calculatedNumbers = new int[n + 1];
// Ahora hacemos una pequeña prueba para ver si de verdad funciona...
long startPoint = System.nanoTime();
System.out.println(fiboMemoized(n));
long finishPoint = System.nanoTime();
System.out.println("FiboMemoized tardó: " + (finishPoint - startPoint) + " en ejecutarse!");
startPoint = System.nanoTime();
System.out.println(fibo(n));
finishPoint = System.nanoTime();
System.out.println("Fibo normal tardó: " + (finishPoint - startPoint) + " en ejecutarse!");
}
public static int fiboMemoized(int n) {
/* Ahora se trata de mantener SIEMPRE el array actualizado, así que empezaremos comprobando si
* ya hemos calculado n o no. Recuerda que un array de int se inicializa a 0! Con lo cual, si ya
* hemos calculado el número, no entraremos al primer if y directamente lo devolveremos
*/
if (calculatedNumbers[n] == 0) {
if (n <= 2) {
/* Si n es menor a 2, estamos con los primeros números de fibonaci, que son 0 y 1, así que
* simplemente guardamos el valor de n-1 en nuestros números calculados!
*/
calculatedNumbers[n] = n - 1;
} else {
// Si n es mayor, vamos a calcularlo como siempre, nada raro por aquí
calculatedNumbers[n] = fiboMemoized(n - 1) + fiboMemoized(n - 2);
}
}
// Llegados a este punto, simplemente devolvemos el valor que hayamos guardado al principio!
return calculatedNumbers[n];
}
public static int fibo(int n){
if (n == 1 || n == 2)
return 1;
else
return fibo(n-1) + fibo(n-2);
}
Para que veas el resultado:
Por cierto, tu método para calcular números de fibonacci parece estar incorrecto, ya que el número 43 en la serie de fibonacci es el 267914296! :)