java - suma - serie fibonacci programacion

Recursión vs. Iteración(secuencia de Fibonacci)

Question

Tengo dos métodos diferentes, uno es calcular la secuencia de Fibonacci para el elemento n mediante el uso de iteración y el otro está haciendo lo mismo con el método recursivo.

El ejemplo del programa se ve así:

import java.util.Scanner;
public class recursionVsIteration {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//nth element input
System.out.print("Enter the last element of Fibonacci sequence: ");
int n = sc.nextInt();
//Print out iteration method
System.out.println("Fibonacci iteration:");
long start = System.currentTimeMillis();
System.out.printf("Fibonacci sequence(element at index %d) = %d /n", n, fibIteration(n));
System.out.printf("Time: %d ms/n", System.currentTimeMillis() - start);
//Print out recursive method
System.out.println("Fibonacci recursion:");
start = System.currentTimeMillis();
System.out.printf("Fibonacci sequence(element at index %d) = %d /n", n, fibRecursion(n));
System.out.printf("Time: %d ms/n", System.currentTimeMillis() - start);
}
//Iteration method
static int fibIteration(int n) {
int x = 0, y = 1, z = 1;
for (int i = 0; i < n; i++) {
x = y;
y = z;
z = x + y;
}
return x;
}
//Recursive method
static int fibRecursion(int n) {
if ((n == 1) || (n == 0)) {
return n;
}
return fibRecursion(n - 1) + fibRecursion(n - 2);
}
}

Estaba tratando de averiguar qué método es más rápido. Llegué a la conclusión de que la recursión es más rápida para la menor cantidad de números, pero a medida que aumenta el valor del elemento n , la recursión se vuelve más lenta y la iteración se vuelve más rápida. Aquí están los tres resultados diferentes para tres n diferentes:

Ejemplo # 1 (n = 10)

Enter the last element of Fibonacci sequence: 10
Fibonacci iteration:
Fibonacci sequence(element at index 10) = 55
Time: 5 ms
Fibonacci recursion:
Fibonacci sequence(element at index 10) = 55
Time: 0 ms

Ejemplo # 2 (n = 20)

Enter the last element of Fibonacci sequence: 20
Fibonacci iteration:
Fibonacci sequence(element at index 20) = 6765
Time: 4 ms
Fibonacci recursion:
Fibonacci sequence(element at index 20) = 6765
Time: 2 ms

Ejemplo # 3 (n = 30)

Enter the last element of Fibonacci sequence: 30
Fibonacci iteration:
Fibonacci sequence(element at index 30) = 832040
Time: 4 ms
Fibonacci recursion:
Fibonacci sequence(element at index 30) = 832040
Time: 15 ms

Lo que realmente quiero saber es por qué de repente una iteración se hizo más rápida y la recursión se hizo más lenta. Lo siento si me perdí una respuesta obvia a esta pregunta, pero todavía soy nuevo en la programación, realmente no entiendo qué está pasando detrás de eso y me gustaría saberlo. Por favor, proporcione una buena explicación o indíqueme la dirección correcta para que yo pueda encontrar la respuesta yo mismo. Además, si esta no es una buena manera de probar qué método es más rápido, avíseme y sugiérame un método diferente.

¡Gracias por adelantado!

Answer 1

Al realizar la implementación recursiva del algoritmo de fibonacci, está agregando llamadas redundantes volviendo a calcular los mismos valores una y otra vez.

fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)

Tenga en cuenta que fib(2) se calculará de forma redundante tanto para fib(4) como para fib(3) . Sin embargo, esto puede superarse con una técnica llamada Memoization , que mejora la eficiencia de la fibonacci recursiva al almacenar los valores, que ha calculado una vez. Las llamadas adicionales de fib(x) para valores conocidos pueden ser reemplazadas por una búsqueda simple, eliminando la necesidad de llamadas recursivas adicionales.

Esta es la principal diferencia entre los enfoques iterativos y recursivos. Si está interesado, también existen otros algoritmos más eficientes para calcular los números de fibonacci.

Answer 2

El enfoque recursivo que utiliza no es eficiente. Le sugiero que use la recursión de la cola. En contraste con su aproximación, la recursión de la cola mantiene solo una llamada de función en la pila en cualquier momento.

public static int tailFib(int n) {
if (n <= 1) {
return n;
}
return tailFib(0, 1, n);
}
private static int tailFib(int a, int b, int count) {
if(count <= 0) {
return a;
}
return tailFib(b, a+b, count-1);
}
public static void main(String[] args) throws Exception{
for (int i = 0; i <10; i++){
System.out.println(tailFib(i));
}
}

Answer 3

Para la terseness, sea F (x) la Fibonacci recursiva

F(10) = F(9) + F(8)
F(10) = F(8) + F(7) + F(7) + F(6)
F(10) = F(7) + F(6) + F(6) + F(5) + 4 more calls.
....

Entonces estás llamando a F (8) dos veces, F (7) 3 veces, F (6) 5 veces, F (5) 7 veces ... y así sucesivamente

Así que con entradas más grandes, el árbol crece más y más.

Answer 4

Prefiero usar una solución matemática usando el número de oro. disfrutar

private static final double GOLDEN_NUMBER = 1.618d;
public long fibonacci(int n) {
double sqrt = Math.sqrt(5);
double result = Math.pow(GOLDEN_NUMBER, n);
result = result - Math.pow(1d - GOLDEN_NUMBER, n);
result = Math.round(result / sqrt);
return Double.valueOf(result).longValue();
}

Answer 5

Si alguien está interesado en una función iterativa con matriz:

public static void fibonacci(int y)
{
int[] a = new int[y+1];
a[0] = 0;
a[1] = 1;
System.out.println("Step 0: 0");
System.out.println("Step 1: 1");
for(int i=2; i<=y; i++){
a[i] = a[i-1] + a[i-2];
System.out.println("Step "+i+": "+a[i]);
}
System.out.println("Array size --> "+a.length);
}

Esta solución se bloquea para el valor de entrada 0 .

Motivo: la matriz a se inicializará 0+1=1 pero la asignación consecutiva de a[1] dará como resultado una excepción de índice fuera de límites.

Agregue una instrucción if que devuelva 0 en y=0 o inicie la matriz con y+2 , lo que desperdiciará 1 int, pero seguirá teniendo un espacio constante y no cambiará la O grande.

Answer 6

Siempre que esté buscando tiempo para completar un algoritmo en particular, es mejor que siempre vaya por la complejidad del tiempo.

Evalúe la complejidad del tiempo en el papel en términos de O (algo).

Comparando los dos enfoques anteriores, la complejidad temporal del enfoque iterativo es O (n), mientras que la del enfoque recursivo es O (2 ^ n).

Tratemos de encontrar la complejidad temporal de fib(4)

Enfoque iterativo, el bucle se evalúa 4 veces, por lo que su complejidad de tiempo es O(n) .

Enfoque recursivo,

 fib(4)
fib(3) + fib(2)
fib(2) + fib(1) fib(1) + fib(0)
fib(1) + fib(0)

de modo que fib () se llama 9 veces, que es ligeramente inferior a 2 ^ n cuando el valor de n es grande, incluso pequeño (recuerde que BigOh (O) se encarga del upper bound ).

Como resultado podemos decir que el enfoque iterativo se está evaluando en el polynomial time , mientras que el recursivo se está evaluando en el exponential time

Answer 7

Tengo una solución recursiva en la que se almacenan los valores calculados para evitar los cálculos innecesarios. El código se proporciona a continuación,

public static int fibonacci(int n) {
if(n <= 0) return 0;
if(n == 1) return 1;
int[] arr = new int[n+1];
// this is faster than using Array
// List<Integer> lis = new ArrayList<>(Collections.nCopies(n+1, 0));
arr[0] = 0;
arr[1] = 1;
return fiboHelper(n, arr);
}
public static int fiboHelper(int n, int[] arr){
if(n <= 0) {
return arr[0];
}
else if(n == 1) {
return arr[1];
}
else {
if( arr[n-1] != 0 && (arr[n-2] != 0 || (arr[n-2] == 0 && n-2 == 0))){
return arr[n] = arr[n-1] + arr[n-2];
}
else if (arr[n-1] == 0 && arr[n-2] != 0 ){
return arr[n] = fiboHelper(n-1, arr) + arr[n-2];
}
else {
return arr[n] = fiboHelper(n-2, arr) + fiboHelper(n-1, arr );
}
}
}

Answer 8

Usando la recursión de la forma que tiene, la complejidad del tiempo es O(fib(n)) que es muy costosa. El método iterativo es O(n) Esto no se muestra porque a) sus pruebas son muy cortas, el código ni siquiera se compilará b) usó números muy pequeños.

Ambos ejemplos serán más rápidos cuanto más los ejecutes. Una vez que un bucle o método ha sido llamado 10,000 veces, debe compilarse a código nativo.

Answer 9

Este artículo hace una comparación entre la recursión y la iteración y cubre su aplicación en la generación de números de fibonacci.

Como se señala en el artículo,

La razón del bajo rendimiento es el gran impulso de los registros en el nivel negativo de cada llamada recursiva.

que básicamente dice que hay más gastos generales en el método recursivo.

Además, echa un vistazo a Memoization

Answer 10

¿Por qué es más lenta la recursión?

Cuando vuelves a llamar a tu función (como recursión), el compilador asigna un nuevo Registro de activación (solo piensa como una pila ordinaria) para esa nueva función. Esa pila se utiliza para mantener sus estados, variables y direcciones. El compilador crea una pila para cada función y este proceso de creación continúa hasta que se alcanza el caso base. Por lo tanto, cuando el tamaño de los datos aumenta, el compilador necesita un gran segmento de pila para calcular todo el proceso. El cálculo y la gestión de esos registros también se cuentan durante este proceso.

Además, en recursión, el segmento de pila se está elevando durante el tiempo de ejecución . El compilador no sabe cuánta memoria estará ocupada durante el tiempo de compilación .

Es por eso que si no puede manejar adecuadamente su caso Base , sufrirá un error famoso llamado :).