Prefácio
Vi esse conteúdo recentemente quando estava lendo um livro e me senti bastante gratificante. A iteração usa um loop (para, enquanto, faz ... wile) ou um iterador, que sai quando a condição do loop não é atendida. A recursão geralmente é uma recursão de função, que pode ser chamada por si mesma ou não diretamente, ou seja, o método A Método B e o Método B chama o método A por sua vez, e a condição para saída recursiva é se e eliminando a declaração, e sai quando a condição atende à base.
O exposto acima são as características da sintaxe da iteração e recursão. Quais são as diferenças entre eles em Java? Vamos aprender mais sobre este artigo abaixo.
1. Recursão
Quando se trata de iteração, temos que mencionar uma expressão matemática: n!=n*(n-1)*(n-2)*...*1
Existem muitas maneiras de calcular fatoriais. Qualquer pessoa com uma certa base matemática conhece n!=n*(n-1)! Portanto, a implementação do código pode ser escrita diretamente como:
Código 1
int fatorial (int n) {if (n == 1) {return 1; } else {return n*fatorial (n-1); }} Ao executar o código acima, a máquina realmente precisa executar uma série de multiplicações: factorial(n) → factorial(n-1) → factorial(n-2) →… → factorial(1) . Portanto, é necessário acompanhar (rastrear o resultado do último cálculo) e a multiplicação de chamadas para executar cálculos (construa uma cadeia de multiplicação). Esse tipo de operação que se chama constantemente é chamado de recursão. A recursão pode ser dividida em recursão linear e recursão numérica. A quantidade de informações aumenta linearmente com a entrada do algoritmo. A recursão é chamada de recursão linear. Calcule n! (fábrica) é uma recursão linear. Porque à medida que N aumenta, o tempo necessário para o cálculo aumenta linearmente. Outro tipo de informação que cresce exponencialmente com o aumento da entrada é chamado recursão de árvore.
2. Iteração
Outra maneira de calcular n! IS: primeiro calcule 1 multiplique por 2, multiplique o resultado por 3 e, em seguida, multiplique o resultado por 4 ... e multiplique até N. Durante a implementação do programa, um contador pode ser definido. Cada vez que a multiplicação é realizada, o contador é incrementado uma vez até que o valor do contador seja igual a N. O código é o seguinte:
Código dois
int fatorial (int n) {int produto = 1; for (int i = 2; i <n; i ++) {produto *= i; } retornar produto;}Comparado com o código um, o código dois não cria uma cadeia de multiplicação. Ao executar cada etapa do cálculo, você só precisa conhecer o resultado atual (produto) e os valores de i. Esta forma de cálculo é chamada de iteração. Existem várias condições para iteração: 1. Existe uma variável com um valor inicial. 2. Uma regra que explica como os valores variáveis são atualizados. 3. Uma condição final. (Três elementos do loop: variáveis de loop, corpos de loop e condições de terminação de loop). O mesmo que a recursão. O requisito de tempo que se torna linear à medida que a entrada cresce linearmente pode ser chamado de iteração linear.
3. Iteração vs. recursão
Depois de comparar os dois programas, podemos descobrir que eles parecem quase os mesmos, especialmente em termos de suas funções matemáticas. Ao calcular N!, Suas etapas de cálculo são proporcionais ao valor de n. No entanto, se assumirmos a perspectiva do programa e considerarmos como eles correm, os dois algoritmos são muito diferentes.
(Nota: o texto original é um pouco irrelevante sobre a diferença, então não vou traduzi -lo aqui. A seguir, é apresentado o próprio resumo do autor.)
Primeiro de tudo, analise a recursão. De fato, a maior coisa sobre recursão é decompor um algoritmo complexo em várias etapas repetíveis idênticas. Portanto, o uso da recursão para implementar uma lógica computacional geralmente requer apenas um código muito curto para resolver, e esse código é mais fácil de entender. No entanto, a recursão significa um grande número de chamadas de função. A razão pela qual o estado local de uma chamada é registrado usando uma pilha. Portanto, isso pode desperdiçar muito espaço e, se a recursão for muito profunda, pode causar transbordamento de pilha.
Em seguida, analise as iterações. De fato, a recursão pode ser substituída pela iteração. No entanto, em comparação com a simplicidade e compreensão da recursão, a iteração é mais rígida e difícil de entender. Especialmente ao encontrar um cenário mais complexo. No entanto, a dificuldade de entender o código também traz pontos mais óbvios. A eficiência da iteração é maior que a recursão e também é relativamente pequena no consumo espacial.
Deve haver iterações na recursão, mas pode não haver recursões nas iterações, e a maioria delas pode ser convertida uma à outra.
Se você pode usar a iteração, não use a recursão. Chamar funções recursivamente não apenas desperdiça espaço, mas também pode causar facilmente transbordamento de pilha se a recursão for muito profunda.
4. Recursão de números
Como mencionado anteriormente, a quantidade de informações que a árvore recursiva aumenta exponencialmente com o aumento da entrada. A sequência de Fibonacci é um exemplo típico:
Na descrição do texto, a soma dos dois primeiros números na sequência de Fibonacci é igual ao terceiro número: 0, 1, 1, 2, 2, 3, 5, 8, 13, 21 ...
O código de implementação recursivo é o seguinte:
int fib (int n) {if (n == 0) {return 0; } else if (n == 1) {return 1; } else {return fib (n-1) + fib (n-2); }} Durante o processo de cálculo, para calcular fib(5) , o programa deve primeiro calcular fib(4) e fib(3) . Para calcular fib(4) , o programa também precisa calcular fib(3) e fib(2) primeiro. FIB (3) é calculado duas vezes durante esse processo.
A partir do processo de cálculo analisado acima, podemos tirar uma conclusão: existe um cálculo redundante para a sequência de Fibonacci usando a recursão.
Como mencionado acima, os algoritmos recursivos geralmente podem ser implementados por iterativamente, e o mesmo se aplica aos cálculos de sequência de Fibonacci.
int fib (int n) {int fib = 0; int a = 1; for (int i = 0; i <n; i ++) {int temp = fib; fib = fib + a; a = temp; } retornar fib;}Embora haja cálculos redundantes no método de recursão, ele pode ser substituído pela iteração. Mas isso não significa que a recursão pode ser completamente substituída. Porque a recursão tem melhor legibilidade.
Resumir
O acima é o conteúdo inteiro deste artigo. Espero que o conteúdo deste artigo seja útil para todos para aprender ou usar o Java. Se você tiver alguma dúvida, pode deixar uma mensagem para se comunicar.