La diferencia entre recursividad e iteración

En resumen, la llamada recursividad significa que la aplicación se llama a sí misma para implementar consultas y acceso a la estructura de datos jerárquica. El uso de la recursividad puede hacer que el código sea más conciso y más fácil de leer (no necesariamente para principiantes), pero debido a que la recursividad requiere una pila del sistema, el consumo de espacio es mucho mayor que el del código no recursivo. , los recursos del sistema pueden ser insuficientes.

A menudo existe la opinión de que la recursividad se puede evitar y que la recursividad se puede reemplazar por la iteración.

Es cierto que, en teoría, la recursividad y la iteración son equivalentes en términos de complejidad temporal (independientemente de la sobrecarga de las llamadas a funciones y la sobrecarga de pila generada por las llamadas a funciones), pero de hecho, la recursividad no es tan eficiente. como iteración. En este caso, la recursividad no tiene ninguna ventaja, por lo que no es necesario utilizarla. ¿Cuál es el punto de la recursividad? La existencia de todas las cosas requiere tiempo para ser probada. La recursividad está enterrada por la historia o tiene una razón para su existencia.

Teóricamente todas las funciones recursivas se pueden convertir en funciones iterativas y viceversa, pero el coste suele ser mayor. Sin embargo, en términos de estructura de algoritmo, las estructuras declaradas recursivamente no siempre se pueden convertir en estructuras iterativas, porque la expansión de la estructura en sí es un concepto recursivo y no se puede lograr mediante métodos iterativos en las primeras etapas del diseño, al igual que el polimorfismo dinámico no lo es. Siempre es posible mediante el polimorfismo estático y se implementa de la misma manera.

Esta es también la razón por la que se suelen utilizar métodos recursivos en lugar de métodos iterativos en el diseño estructural. Un ejemplo típico es similar a una lista vinculada, que utiliza una definición recursiva, que es muy simple, pero su definición de definición de memoria (método de matriz) y las instrucciones de procesamiento de llamadas se vuelven muy confusas, especialmente cuando se encuentran problemas como cadenas circulares, gráficos, cuadrículas, etc. Usar un enfoque iterativo desde la descripción hasta la implementación se vuelve poco realista. Entonces, en realidad, todas las iteraciones se pueden convertir en recursiones, pero las recursiones no necesariamente se pueden convertir en iteraciones.

El requisito previo para usar el algoritmo recursivo es que el algoritmo recursivo se pueda usar solo si uno tiene la convergencia deseada. De lo contrario, el algoritmo recursivo no se puede usar.

La recursividad es realmente muy conveniente para los programadores. La recursividad se puede convertir fácilmente en un programa mediante fórmulas matemáticas. La ventaja es que es fácil de entender y programar. La recursividad se implementa a través del mecanismo de pila y cada paso en profundidad ocupa un área de datos de la pila. Para algunos algoritmos con niveles de anidamiento más profundos, la recursividad no será suficiente y el espacio terminará en un colapso de la memoria. La recursividad también traerá una gran cantidad de llamadas a funciones y una gran cantidad de tiempo adicional. Entonces, cuanto mayor es la profundidad, peor es su espacio y tiempo.

Aunque la iteración es eficiente, solo aumenta el tiempo de ejecución al aumentar el número de bucles. Sin embargo, la desventaja es que no es fácil de entender. Es difícil escribir problemas complejos.

Por lo tanto, la comprensión de "la recursividad se puede evitar y la recursividad se puede reemplazar por iteración" sigue siendo dialéctica y no se puede matar a golpes con un palo.