Prefacio
Vi este contenido recientemente cuando estaba leyendo un libro y me sentí bastante gratificante. La iteración usa un bucle (para, mientras, do ... wile) o un iterador, que sale cuando no se cumple la condición de bucle. La recursión es generalmente una recursión de función, que puede llamarse por sí misma o no directamente, es decir, el método A Llamadas B, y el método B llama Método A a su vez, y la condición para la salida recursiva es si y de lo contrario, y sale cuando la condición cumple con la base.
Lo anterior son las características de sintaxis de la iteración y la recursión. ¿Cuáles son las diferencias entre ellos en Java? Aprendamos más sobre este artículo a continuación.
1. Recursión
Cuando se trata de iteración, tenemos que mencionar una expresión matemática: n!=n*(n-1)*(n-2)*...*1
Hay muchas formas de calcular los factorales. ¡Cualquiera con cierta base matemática sabe n!=n*(n-1)! Por lo tanto, la implementación del código se puede escribir directamente como:
Código 1
int factorial (int n) {if (n == 1) {return 1; } else {return n*factorial (n-1); }} Al ejecutar el código anterior, la máquina en realidad necesita realizar una serie de multiplicaciones: factorial(n) → factorial(n-1) → factorial(n-2) → ... → factorial(1) . Por lo tanto, es necesario realizar un seguimiento de (rastrear el resultado del último cálculo) y la multiplicación de llamadas para realizar cálculos (construir una cadena de multiplicación). Este tipo de operación que se llama constantemente se llama recursión. La recursión se puede dividir en recursión lineal y recursión numérica. La cantidad de información aumenta linealmente con la entrada del algoritmo. La recursión se llama recursión lineal. Calcule n! (fábrica) es recursión lineal. Porque a medida que aumenta N, el tiempo requerido para el cálculo aumenta linealmente. Otro tipo de información que crece exponencialmente con el aumento de la entrada se llama recursión de árbol.
2. Iteración
¡Otra forma de calcular n! IS: primero calcule 1 multiplicar por 2, luego multiplique el resultado por 3 y luego multiplique el resultado por 4 ... y multiplique hasta N. Durante la implementación del programa, se puede definir un contador. Cada vez que se realiza la multiplicación, el contador se incrementa una vez hasta que el valor del contador sea igual a N. El código es el siguiente:
Código dos
int factorial (int n) {int producto = 1; para (int i = 2; i <n; i ++) {producto *= i; } producto de retorno;}En comparación con el código uno, el código dos no crea una cadena de multiplicación. Al realizar cada paso de cálculo, solo necesita conocer el resultado actual (producto) y los valores de i. Esta forma de cálculo se llama iteración. Hay varias condiciones para la iteración: 1. Hay una variable con un valor inicial. 2. Una regla que explica cómo se actualizan los valores variables. 3. Una condición final. (Tres elementos del bucle: variables de bucle, cuerpos de bucle y condiciones de terminación de bucle). Igual que la recursión. El requisito de tiempo que se vuelve lineal a medida que la entrada crece linealmente puede llamarse iteración lineal.
3. Iteración vs. recursión
Después de comparar los dos programas, podemos encontrar que se ven casi lo mismo, especialmente en términos de sus funciones matemáticas. Al calcular n!, Sus pasos de cálculo son proporcionales al valor de n. Sin embargo, si tomamos la perspectiva del programa y consideramos cómo se ejecutan, entonces los dos algoritmos son muy diferentes.
(Nota: el texto original es un poco irrelevante sobre la diferencia, por lo que no lo traduciré aquí. El siguiente es el propio resumen del autor).
En primer lugar, analice la recursión. De hecho, lo más importante de la recursión es descomponer un algoritmo complejo en varios pasos repetibles idénticos. Por lo tanto, el uso de la recursión para implementar una lógica computacional a menudo requiere solo un código muy corto para resolver, y dicho código es más fácil de entender. Sin embargo, la recursión significa una gran cantidad de llamadas de funciones. La razón por la cual el estado local de una llamada de función se registra utilizando una pila. Por lo tanto, esto puede desperdiciar mucho espacio, y si la recursión es demasiado profunda, puede causar desbordamiento de pila.
A continuación, analice las iteraciones. De hecho, la recursión puede ser reemplazada por la iteración. Sin embargo, en comparación con la simplicidad y comprensión de la recursión, la iteración es más rígida y difícil de entender. Especialmente al encontrar un escenario más complejo. Sin embargo, la dificultad de comprender el código también trae puntos más obvios. La eficiencia de la iteración es más alta que la recursión y también es relativamente pequeña en el consumo de espacio.
Debe haber iteraciones en la recursión, pero puede que no haya recursiones en las iteraciones, y la mayoría de ellas pueden convertirse entre sí.
Si puede usar la iteración, no use la recursión. Llamar a las funciones de forma recursiva no solo desperdicia espacio, sino que también puede causar fácilmente el desbordamiento de la pila si la recursión es demasiado profunda.
4. Recursión de números
Como se mencionó anteriormente, la cantidad de información que el árbol recursiva aumenta exponencialmente con el aumento de la entrada. La secuencia de Fibonacci es un ejemplo típico:
En la descripción del texto, la suma de los dos primeros números en la secuencia de Fibonacci es igual al tercer número: 0, 1, 1, 2, 3, 5, 8, 13, 21 ...
El código de implementación recursivo es el siguiente:
int fib (int n) {if (n == 0) {return 0; } else if (n == 1) {return 1; } else {return fib (n-1) + fib (n-2); }} Durante el proceso de cálculo, para calcular fib(5) , el programa primero debe calcular fib(4) y fib(3) . Para calcular fib(4) , el programa también necesita calcular fib(3) y fib(2) primero. FIB (3) se calcula dos veces durante este proceso.
Del proceso de cálculo analizado anteriormente, podemos sacar una conclusión: existe un cálculo redundante para la secuencia Fibonacci utilizando la recursión.
Como se mencionó anteriormente, los algoritmos recursivos generalmente se pueden implementar por iterativamente, y lo mismo es cierto para los cálculos de secuencia Fibonacci.
int fib (int n) {int fib = 0; int a = 1; para (int i = 0; i <n; i ++) {int temp = fib; fib = fib + a; a = temp; } return fib;}Aunque habrá cálculos redundantes en el método de recursión, puede reemplazarse por la iteración. Pero esto no significa que la recursión pueda reemplazarse por completo. Porque la recursión tiene una mejor legibilidad.
Resumir
Lo anterior es todo el contenido de este artículo. Espero que el contenido de este artículo sea útil para todos en aprender o usar Java. Si tiene alguna pregunta, puede dejar un mensaje para comunicarse.