Recursão vs. Iteração (sequência de Fibonacci)

Eu tenho dois methods diferentes, um é calcular a seqüência de Fibonacci para o enésimo elemento usando iteração e o outro está fazendo a mesma coisa usando o método recursivo.


Exemplo de programa é assim:

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); } } 

Eu estava tentando descobrir qual método é mais rápido. Cheguei à conclusão de que a recursion é mais rápida para a menor quantidade de números, mas como o valor do elemento nés aumenta, a recursion se torna mais lenta e a iteração se torna mais rápida. Aqui estão os três resultados diferentes para três n diferentes:


Exemplo # 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 

Exemplo # 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 

Exemplo # 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 

O que eu realmente quero saber é por que, de repente, a iteração se tornou mais rápida e a recursion se tornou mais lenta. Me desculpe se eu perdi alguma resposta óbvia para esta pergunta, mas eu ainda sou novo na programação, eu realmente não entendo o que está acontecendo por trás disso e eu gostaria de saber. Por favor, forneça uma boa explicação ou aponte-me na direção certa para que eu possa descobrir a resposta sozinho. Além disso, se isso não é uma boa maneira de testar qual método é mais rápido, deixe-me saber e me sugerir método diferente.

Desde já, obrigado!

Para terseness, Deixe F (x) ser o Fibonacci recursivo

 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. .... 

Então você está chamando F (8) duas vezes, F (7) 3 vezes, F (6) 5 vezes, F (5) 7 vezes … e assim por diante

Assim, com insumos maiores, a tree fica maior e maior.

Este artigo faz uma comparação entre recursion e iteração e abrange sua aplicação na geração de números de fibonacci.

Conforme observado no artigo,

A razão para o fraco desempenho é o grande aumento dos registros no nível negativo de cada chamada recursiva.

que basicamente diz que há mais sobrecarga no método recursivo.

Além disso, dê uma olhada no Memoization

Ao fazer a implementação recursiva do algoritmo fibonacci, você está adicionando chamadas redundantes recalculando os mesmos valores repetidamente.

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

Observe que fib(2) será calculado redundantemente tanto para fib(4) quanto para fib(3) . No entanto, isso pode ser superado por uma técnica chamada Memoization , que melhora a eficiência de fibonacci recursivo armazenando os valores, você calculou uma vez. Outras chamadas de fib(x) para valores conhecidos podem ser substituídas por uma simples pesquisa, eliminando a necessidade de mais chamadas recursivas.

Esta é a principal diferença entre as abordagens iterativa e recursiva, se você estiver interessado, há também outros algoritmos mais eficientes de calcular números de fibonacci.

Usando a recursion do jeito que você tem, a complexidade do tempo é O(fib(n)) que é muito cara. O método iterativo é O(n) Isso não aparece porque a) seus testes são muito curtos, o código nem será compilado b) você usou números muito pequenos.

Ambos os exemplos se tornarão mais rápidos quanto mais você os executar. Uma vez que um loop ou método tenha sido chamado 10.000 vezes, ele deve ser compilado para o código nativo.

Por que a recursion é mais lenta?

Quando você chama sua function novamente (como recursion), o compilador aloca o novo Registro de Ativação (pense apenas como uma Pilha comum) para essa nova function. Essa pilha é usada para manter seus estados, variables ​​e endereços. O compilador cria uma pilha para cada function e esse processo de criação continua até que o caso base seja atingido. Portanto, quando o tamanho dos dados se torna grande, o compilador precisa de um segmento de pilha grande para calcular todo o processo. O cálculo e o gerenciamento desses registros também são contados durante esse processo.

Além disso, na recursion, o segmento da pilha está sendo gerado durante o tempo de execução . O compilador não sabe quantas memory será ocupada durante o tempo de compilation .

É por isso que, se você não puder manipular corretamente o seu caso Base, você passará por um famoso erro chamado StackOverflow :).

Se alguém estiver interessado em uma function iterativa com 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 solução falha para o valor de input 0 .

Razão: A matriz a será inicializada 0+1=1 mas a atribuição consecutiva de a[1] resultará em uma exceção de índice fora dos limites.

Adicione uma instrução if que retorne 0 em y=0 ou inicialize a matriz por y+2 , o que desperdiçará 1 int, mas ainda será de espaço constante e não alterará O grande.

Eu prefiro usar uma solução matemática usando o número de ouro. apreciar

 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(); } 

A abordagem recursiva que você usa não é eficiente. Eu sugiro que você use recursion de cauda. Ao contrário da sua abordagem, a recursion da cauda mantém apenas uma chamada de function na pilha a qualquer 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)); } } 

Sempre que você está procurando tempo para completar um algoritmo específico, é melhor você sempre ir para a complexidade do tempo.

Avalie a complexidade do tempo no papel em termos de O (alguma coisa).

Comparando as duas abordagens acima, a complexidade temporal da abordagem iterativa é O (n) enquanto que a abordagem recursiva é O (2 ^ n).

Vamos tentar encontrar a complexidade do tempo da fib(4)

A abordagem iterativa, o loop avalia 4 vezes, por isso, a complexidade do tempo é O(n) .

Abordagem recursiva,

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

então fib () é chamado 9 vezes o que é um pouco menor que 2 ^ n quando o valor de n é grande, mesmo pequeno também (lembre-se que BigOh (O) cuida do upper bound ).

Como resultado podemos dizer que a abordagem iterativa está avaliando em polynomial time , enquanto a recursiva está avaliando em exponential time

Eu tenho uma solução recursiva que você onde os valores calculados são armazenados para evitar os cálculos desnecessários adicionais. O código é fornecido abaixo,

 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 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 ); } } } 
Intereting Posts