Para determinar si un algoritmo recursivo o iterativo es más eficiente sin escribir ambas implementaciones y perfilar el código resultante, puede tomar una estimación aproximada del dedo en el viento determinando ciertas medidas de eficiencia del algoritmo teórico (por ejemplo, la notación “O grande”) .
Sin embargo, para hacer esto con mayor precisión, debe comprender algunos detalles sobre la cadena de herramientas y la arquitectura de destino y la plataforma de hardware con la que está trabajando, con resultados que pueden variar enormemente dependiendo de esos detalles.
Uno de los ejemplos más obvios sería que muchos lenguajes (ya sea por especificación o en implementaciones específicas) no implementan la optimización de llamadas de cola. En estos casos, un algoritmo cuya implementación iterativa no requiera el mantenimiento de una pila o lista para mantener el estado (es decir, aquellos que pueden traducirse trivialmente en forma recursiva de llamada de cola) será casi seguro superior a una versión recursiva porque la implementación requerirá creación de un marco de pila para cada llamada recursiva sucesiva, incluso si no se requiere teóricamente.
- ¿Cuál es el patrón de promesa?
- ¿Cuál es el número promedio de proyectos en los que se espera que un ingeniero de software trabaje simultáneamente en su trabajo?
- ¿Cómo prueba la validez del HTML generado por taglibs o código de representación HTML en sus aplicaciones?
- ¿Cuáles son algunas de las fallas más grandes debido a la mala calidad del código?
- ¿Debo seguir una carrera en informática forense o ingeniería de software?
Las cosas pueden ponerse mucho más difíciles y más difíciles de predecir cuando ciertas clases de optimizaciones del compilador podrían haberse implementado, pero las optimizaciones no son aplicables a una forma u otra porque solo ciertos tipos de estructuras en los AST u otras representaciones intermedias son reconocidas por algoritmos de optimización (la falta de optimización de llamadas de cola a veces es posiblemente un ejemplo específico de esta clase de problema).
Entonces, para saber cuál será mejor sin escribirlos, debe sentirse muy cómodo con la especificación del idioma y los detalles de la implementación específica del idioma con el que está trabajando, y tal vez incluso la configuración / opciones utilizadas para compilar o ejecutar el código. Por ejemplo, si es un código C que se compilará usando gcc con -funroll-loops, podría utilizar totalmente el rendimiento de un algoritmo iterativo si, en su plataforma de destino, el código resultante causa un aumento en la memoria caché de instrucciones como resultado.
En la práctica, si realmente es tan importante determinar si un algoritmo iterativo o recursivo es mejor (suponiendo que ambos logren lo mismo), realmente debería escribir y perfilar ambos.
Editar:
Después de escribir esta respuesta, se me ocurrió que sería casi desmesurado no tener en cuenta que, fuera de los ejemplos extremadamente raros o artificiales, la posibilidad de que las diferencias de eficiencia de rendimiento entre un algoritmo recursivo o iterativo realmente dicte la elección de ir con uno versus el otro es básicamente 0%. Si incluso tiene que hacerse esta pregunta, NO base su decisión en su conjetura sobre cuál será más eficiente. En su lugar, céntrelo en cuál entiende y puede escribir más claramente. Si tiene que hacer esta pregunta “legítimamente”, entonces está realmente más en el ámbito de si debe o no elaborar a mano algún asm en línea o un kernel fortan o C al que se accede a través del FFI de su idioma o algo así. .