Bueno, mucho depende de los detalles de implementación del lenguaje de programación. Algunas implementaciones de lenguaje de programación proporcionan optimización de recursión de cola, por lo que una recursión de cola se compila para ser exactamente una iteración. Incluso hay idiomas en los que la recursividad de cola es cómo se especifica un algoritmo iterativo. Pero en un lenguaje como las versiones actuales de Python, que no proporcionan una optimización de recursión de cola, debe tener cuidado de no engullir y desbordar el espacio de la pila recurriendo demasiado profundamente. Entonces, para una n pequeña, puede usar la recursión o puede usar la iteración, pero para una n más grande, que generalmente agrega otra capa de recursión con cada duplicación de n, tal vez necesite encontrar una solución iterativa al problema que está resolviendo.
Mucho antes de pasar por alto detalles como minimizar las fallas de caché, el primer objetivo es obtener un programa que funcione correctamente. Algunos problemas se expresan mejor en términos recursivos (por ejemplo, ordenar 1 cosa es trivial, por lo que puede ser el caso base no recurrente). Dadas 2 listas ordenadas, es fácil combinarlas en una lista ordenada más grande, por lo que si comienza con la necesidad de ordenar una lista de n elementos, divídala en listas de 2 n / 2 y clasifique cada una de ellas, luego combine 2. ¿Cómo se ordena una lista de n / 2 elementos? Bueno, si n / 2 = 1, simplemente devuelve esa lista de 1 elemento como si ya estuviera en orden. Si n / 2> 1, use recursivamente esta misma rutina de clasificación para ordenar las 2 listas más pequeñas, luego combine las 2 listas más pequeñas ordenadas. La fusión es probablemente la más fácil de expresar como una iteración. Para cuando todo esto funcione, funciona incluso con valores impares de n que no se dividen por la mitad exactamente, entonces tendrás que decidir si tienes un código lo suficientemente bueno para tus propósitos, o si tiene que optimizarlo para que se ajuste mejor a la memoria caché o algún detalle molesto. Pero ni siquiera piense en optimizar hasta que primero llegue a una implementación funcional.
Si comienza estableciéndose en un orden O (n ** 2) más simple porque usa mera iteración, evitando la posible sobrecarga de recursividad, entonces la complejidad de O (n ** 2) va a importar para valores grandes de n lejos más que errores de caché y todo eso.
- ¿Diferencia entre algoritmo de relleno de inundación y relleno de límite en gráficos de computadora?
- ¿Dónde puedo obtener el algoritmo de 'Biblioteca de Babel'?
- ¿Cuál es el mejor algoritmo para ocultar datos en texto?
- Cómo calcular la complejidad del algoritmo de ordenamiento por selección
- Cómo calcular el gran espacio O de una pila en problemas de retroceso
Si su código recursivo resulta tener una recursión de cola, es bastante simple reescribir el código para que sea una iteración en lugar de una recursión. En algunas implementaciones de lenguaje, esa transformación puede ser una optimización que vale la pena, pero en otras implementaciones de lenguaje, no le comprará nada porque está aplicando manualmente el mismo tipo de transformación al código que las rutinas de optimización del compilador estaban haciendo automáticamente cuando notaron La recursión de cola en su código. Ajustar manualmente el código corre el riesgo de introducir nuevos errores en su código, por lo tanto, a menos que encuentre que la versión transformada sea más fácil de leer, deje el código solo y deje que el optimizador haga la optimización por usted. Eso es legibilidad y corrección son las guías para las elecciones correctas.
Tenga en cuenta que cualquier algoritmo recursivo puede implementarse en un lenguaje que no sea compatible con la recursividad. Tendrá que averiguar qué constituye exactamente el estado de la computación que la rutina necesita para continuar trabajando después de que la llamada recursiva regrese. Luego, cree una pila que usted mismo administre para guardar ese estado, de modo que pueda insertar el estado actual en la pila e iterar en lugar de hacer una llamada recursiva. Cuando llega a un caso base donde la versión recursiva volvería a la persona que llama, la versión no recursiva muestra el estado guardado más recientemente de la pila y completa el procesamiento tal como la versión recurrente continuaría después de que la llamada recursiva haya regresado. Mi punto es que la recursión y la iteración son bastante intercambiables entre sí, siempre que descubra que administrar manualmente el estado del cálculo es un aumento tolerable en la carga de trabajo en el programador.
Resumen:
- Elija un algoritmo que satisfaga sus necesidades o estará condenado desde el principio. O (n ** 2) puede estar bien si sabe que siempre tendrá valores pequeños para n. Recuerda KISS (Hazlo simple …).
- Elija la forma más clara y clara de expresar el algoritmo elegido en su idioma de destino. Hazlo bien antes de preocuparte por optimizar el código. Generalmente legible es un mejor camino hacia la corrección que un lío enredado de código con muchos lugares donde se pueden esconder los errores. Si el paso 2 es difícil, quizás debería reconsiderar cuál es la mejor opción de idioma de destino para usted. En un proyecto grande, esto puede ser un asunto político complicado, pero puede ser una discusión complicada que vale la pena tener.
- Solo después de haber realizado mediciones en su programa correcto, debe pensar en ajustar el código para optimizarlo a mano. Si encuentra que el código pierde su objetivo de rendimiento en gran medida, es posible que desee repensar el paso 1 de esta lista. Tal vez necesite un mejor algoritmo, no solo ajustes de ajuste. No asuma que sus cambios de sintonía siempre mejorarán el rendimiento. Mida antes y mida después para ver que el cambio ayudó. Mantenga sus casos de prueba disponibles para que pueda probar antes y después para asegurarse de que sus cambios conserven la corrección. (Tan fácil de introducir accidentalmente algún retiro de la corrección).
