Serie de Fibonacci en Java utilizando recursión y bucles

¿En qué consiste la serie de Fibonacci? Java?

A Serie de Fibonacci in Java Es una serie de números en la que cada número siguiente es la suma de los dos anteriores. Los dos primeros números de la serie de Fibonacci son 0 y 1. Los números de Fibonacci se utilizan ampliamente en el estudio del tiempo de ejecución computacional del algoritmo que determina el máximo común divisor de dos enteros.

The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Expresada como una fórmula, la regla es F(n) = F(n-1) + F(n-2), con F(0) = 0 y F(1) = 1. La tabla a continuación muestra cómo se producen los primeros ocho términos.

Programa de la serie Fibonacci en Java usando bucle For

La versión iterativa mantiene solo dos valores en memoria en cada momento, por lo que se ejecuta en tiempo lineal y espacio constante.

//Using  For Loop
public class FibonacciExample {
	public static void main(String[] args)
	{
		// Set it to the number of elements you want in the Fibonacci Series
		 int maxNumber = 10;
		 int previousNumber = 0;
		 int nextNumber = 1;
	        System.out.print("Fibonacci Series of "+maxNumber+" numbers:");
	        for (int i = 1; i <= maxNumber; ++i)
	        {
	            System.out.print(previousNumber+" ");
	            /* On each iteration, we are assigning second number
	             * to the first number and assigning the sum of last two
	             * numbers to the second number
	             */


	            int sum = previousNumber + nextNumber;
	            previousNumber = nextNumber;
	            nextNumber = sum;
	        }
	}
}

Salida:

Fibonacci Series of 10 numbers:0 1 1 2 3 5 8 13 21 34

Lógica del programa:

• previousNumber se inicializa a 0 y nextNumber se inicializa a 1.
• El bucle for de Fibonacci itera a través de maxNumber:
  • Mostrar el número anterior.
  • Calcula la suma de previousNumber y nextNumber.
  • Actualiza los nuevos valores de previousNumber y nextNumber.

Programa de la serie Fibonacci en Java usando el bucle while

También puedes generar un Java Serie de Fibonacci utilizando una while incluyete JavaLa aritmética es idéntica, y solo cambia la sintaxis del bucle.

//Using  While Loop
public class FibonacciWhileExample {
	public static void main(String[] args)
	{
		 int maxNumber = 10, previousNumber = 0, nextNumber = 1;
	        System.out.print("Fibonacci Series of "+maxNumber+" numbers:");

	        int i=1;
	        while(i <= maxNumber)
	        {
	            System.out.print(previousNumber+" ");
	            int sum = previousNumber + nextNumber;
	            previousNumber = nextNumber;
	            nextNumber = sum;
	            i++;
	        }

	}

}

Salida:

Fibonacci Series of 10 numbers:0 1 1 2 3 5 8 13 21 34

La única diferencia en la lógica del programa radica en el uso de un bucle while para imprimir los números de Fibonacci. El contador debe declararse antes del bucle e incrementarse dentro del mismo; de lo contrario, el bucle nunca finalizará.

Serie de Fibonacci basada en la entrada del usuario

Codificar el número de términos directamente en el código es práctico para una demostración, pero en ejercicios reales se suele leer el valor desde el teclado. La clase Scanner se encarga de esto en tres líneas, y la lógica de generación permanece intacta.

//fibonacci series based on the user input
import java.util.Scanner;

public class FibonacciUserInput {

    public static void main(String[] args)
    {
        int maxNumber = 0;
        int previousNumber = 0;
        int nextNumber = 1;

        System.out.println("How many numbers you want in Fibonacci:");
        Scanner scanner = new Scanner(System.in);
        maxNumber = scanner.nextInt();
        System.out.print("Fibonacci Series of " + maxNumber + " numbers:");

        for (int i = 1; i <= maxNumber; ++i)
        {
            System.out.print(previousNumber + " ");
            /* On each iteration, we are assigning the second number
             * to the first number and assigning the sum of the last two
             * numbers to the second number
             */

            int sum = previousNumber + nextNumber;
            previousNumber = nextNumber;
            nextNumber = sum;
        }

        scanner.close();
    }
}

Ejecución de ejemplo:

How many numbers you want in Fibonacci:
7
Fibonacci Series of 7 numbers:0 1 1 2 3 5 8

Lógica del programa:
La lógica es la misma que antes. En lugar de codificar de forma fija el número de elementos a mostrar en el Java En la serie de Fibonacci, se le pide al usuario que ingrese un número.

Serie de Fibonacci usando recursividad en Java

A continuación se muestra un programa de series de Fibonacci en Java usando recursividad:

//Using Recursion
public class FibonacciCalc{
	public static int fibonacciRecursion(int n){
	if(n == 0){
		return 0;
	}
	if(n == 1 || n == 2){
			return 1;
		}
	return fibonacciRecursion(n-2) + fibonacciRecursion(n-1);
	}
    public static void main(String args[]) {
	int maxNumber = 10;
	System.out.print("Fibonacci Series of "+maxNumber+" numbers: ");
	for(int i = 0; i < maxNumber; i++){
			System.out.print(fibonacciRecursion(i) +" ");
		}
	}
}

Salida:

Fibonacci Series of 10 numbers: 0 1 1 2 3 5 8 13 21 34

Lógica del programa:

Una función recursiva es aquella que tiene la capacidad de llamarse a sí misma.

Recursión de Fibonacci():

1. El Java La función de recursión de Fibonacci toma un número de entrada. Comprueba si es 0, 1 y 2 y devuelve 0, 1 y 1 respectivamente, porque la secuencia de Fibonacci en Java comienza con 0, 1, 1.
2. Cuando la entrada n es 3 o mayor, la función se llama a sí misma recursivamente. La llamada se realiza dos veces. trace a continuación sigue la solicitud de una entrada de 4.

fibonacciRecursion(4)
    = fibonacciRecursion(2) + fibonacciRecursion(3)

    fibonacciRecursion(2) = 1                    // base case, no further calls
    fibonacciRecursion(3) = fibonacciRecursion(1) + fibonacciRecursion(2)
                          = 1 + 1
                          = 2

    Result: 1 + 2 = 3

Los casos base detienen el descenso. Debido a que 1 y 2 regresan inmediatamente, la rama para fibonacciRecursion(2) nunca se expande más, que es lo que mantiene el trace finito.

Serie de Fibonacci optimizada mediante memorización.

La recursión simple recalcula los mismos términos muchas veces. Calcular el término 40 requiere más de 200 millones de llamadas. Almacenar cada resultado la primera vez que se calcula elimina por completo esa duplicación.

public class FibonacciMemo {

    static long[] cache;

    public static long fib(int n) {
        if (n <= 1) {
            return n;
        }
        // return the stored value when it exists
        if (cache[n] != 0) {
            return cache[n];
        }
        cache[n] = fib(n - 1) + fib(n - 2);
        return cache[n];
    }

    public static void main(String[] args) {
        int maxNumber = 90;
        cache = new long[maxNumber + 1];

        System.out.println("Term 50 is: " + fib(50));
        System.out.println("Term 90 is: " + fib(90));
    }
}

Salida:

Term 50 is: 12586269025
Term 90 is: 2880067194370816120

Comparación de métodos de Fibonacci en Java

Los cuatro programas imprimen la misma secuencia, por lo que la decisión depende de cuántos términos se necesiten.

El mismo patrón de contador y acumulador aparece en varios ejercicios relacionados. Continúe con el Java programa de palíndromos, Java programa para comprobar si un número es primo, y Programa para imprimir números primos del 1 al 100.Para la práctica basada en matrices, consulte Bubble Ordenar en Java y Java arrays, y revisa el para cada bucle en Java para sintaxis de bucle alternativa.

Preguntas Frecuentes