¿Es seguro decir que un algoritmo iterativo es mejor que el recursivo para el mismo problema dado que ambos son de la misma complejidad temporal?

No es seguro decir eso, no.

Existe una idea errónea muy común entre los programadores de la industria de que la recursividad es ineficiente. De lo que no se dan cuenta es que los lenguajes de programación que la mayoría de ellos prefieren usar (Python, PHP, Ruby, Perl) son ineficientes, no el concepto abstracto de recursión. Específicamente, los idiomas de esa lista y muchos otros similares no son compatibles con la optimización de llamadas de cola, lo que elimina el creciente problema del espacio de pila.

Muchos otros idiomas, como Clojure, OCaml, Haskell, SML, Scheme, Racket optimizan las llamadas de cola. Esto significa que mientras su llamada recursiva esté en posición de cola, puede hacer un bucle para siempre y no aumentará la pila, no tendrá un desbordamiento de pila, y su rendimiento será idéntico al de un bucle en la mayoría de esos idiomas .

Siento que es sí.

Debido a la naturaleza recursiva, la complejidad del espacio será mayor que la iterativa.

Sin embargo, la gente podría preferir el recursivo ya que es un poco más fácil de leer, especialmente en programación dinámica.

Una vez que escribí una relación recusiva / función recursiva que es muy simple de entender en la programación dinámica pero falló debido al desbordamiento de la pila. Después de reescribirlo en versión iterativa, pasó fácilmente.

Desde entonces siempre empiezo con recusivo pero termino escribiendo el final como iterativo.

Depende de lo que quieras decir con “mejor”.

Eche un vistazo a (pseudo-Python) Profundidad recursiva Primera búsqueda:

def dfs (inicio: nodo, final: nodo):
si inicio = fin:
salida

start.visit ()

para vecino en start.neighs si neighbor.is_unvisited:
dfs (vecino)

Y ahora en la versión iterativa:

pila = [inicio]

mientras stack.is_not_empty:
nodo = stack.pop ()

si nodo = fin:
salida

node.visit ()

para vecino en node.neighs si neighbor.is_unvisited:
stack.push (vecino)

La versión recursiva es más elegante y fácil de leer y comprender, mientras que la versión iterativa es ligeramente más eficiente e idealmente evita desbordamientos de pila.

La respuesta a su pregunta depende de lo que prefiera más: ¿legibilidad o rendimiento?

Depende del caso en mano.

Si puede implementar una solución utilizando una pila que simule la recursividad, podría obtener un mejor rendimiento ya que se evitan los gastos generales debido a las llamadas a funciones. Además, el tamaño de su pila puede ser mayor que la profundidad de recursión máxima normalmente permitida.

Pero, algunos compiladores proporcionan una optimización específica de la máquina de destino si usa la recursividad de cola en su código. Esta optimización garantiza que solo haya una llamada de función pendiente en el registro de activación en cualquier momento, ahorrando en la profundidad de recursión + otros aspectos de nivel inferior. Por lo tanto, la recursión podría ser preferible en este caso

En un sentido general, un enfoque “iterativo” puede ser más elegante. Pero la mente humana gravita hacia un enfoque recursivo. Lo que hace que la recursividad sea más natural es que sabes exactamente cuándo, cómo se está terminando un bloque de código recursivo y qué identificación llegó a su destino. La segunda parte es que sabes lo que hará en el camino de regreso a medida que se desenrolla. Además, el nombre de la función es un marcador claro en su código. Con un enfoque iterativo no es así y generalmente hay más problemas lógicos invocados. Pero si su código requiere una escalabilidad desconocida o si no conoce las múltiples formas en que su código puede ser “implementado”, entonces “iterativo” es el camino a seguir.

El mayor problema en el enfoque recursivo es el desbordamiento de la pila. Si usamos un algoritmo recursivo para problemas grandes, definitivamente habría un desbordamiento de pila. Podemos usar este enfoque para pequeños problemas.

Sí, es seguro decir que un algoritmo iterativo es mejor que recursivo. Porque nunca causa una condición de desbordamiento de la pila, y también evita la terminación no deseada. Eso es todo según mi opinión.

Diré que ambos son seguros porque no explotarán como un átomo o una bomba de tiempo. Bien, eso es una broma. La recursiva será difícil de implementar. Y muy costoso en términos de espacio de memoria. Pero es mejor ir con uno recursivo si necesita llamar a las mismas funciones n veces.