¿Existen ventajas para el uso de la recursividad sobre la iteración, aparte de la legibilidad y la elegancia a veces? [duplicar]

7

Estoy a punto de hacer dos suposiciones. Por favor, corríjame si están equivocados:

  1. No hay un algoritmo recursivo sin un equivalente iterativo.
  2. La iteración es siempre más barata en cuanto a rendimiento que la recursión (en menos en lenguajes de propósito general como Java, C ++, Python, etc.).

Si es cierto que la recursión siempre es más costosa que la iteración, y que siempre se puede reemplazar con un algoritmo iterativo (en idiomas que lo permitan), creo que las dos razones restantes para usar la recursión son: elegancia y legibilidad .

Algunos algoritmos se expresan de manera más elegante con la recursión. P.ej. escaneando un árbol binario.

Sin embargo, aparte de eso, ¿hay razones para usar la recursión sobre la iteración? ¿La recursión tiene ventajas sobre la iteración aparte de la elegancia y la facilidad de lectura?

    
pregunta Aviv Cohn 03.06.2014 - 17:07

3 respuestas

9

Bueno, generalmente es menos código.

Y en la medida en que es menos código, es menos propenso a errores.

En particular, la recursión es muy beneficiosa cuando las soluciones iterativas requieren que simule recursividad con una pila. Recursion reconoce que el compilador ya administra una pila para lograr exactamente lo que necesita. Cuando comience a administrar el suyo, no solo es probable que esté reintroduciendo la función de sobrecarga de llamadas que pretendía evitar; pero estás reinventando una rueda (con mucho espacio para errores) que ya existe en una forma bastante libre de errores.

OMI, solo evite la recursión si puede hacerse de forma natural y fácil sin una pila. (U otra estructura de administración de ámbito y / o estado no escalar).

    
respondido por el svidgen 03.06.2014 - 18:58
2

La recursión utiliza la pila de llamadas para almacenar devoluciones de llamadas de función. El estado de la función se almacena entre las llamadas.

La iteración también debe usar una pila o algún mecanismo similar para almacenar estados intermedios, excepto que usted mismo cree la pila. Por supuesto, a menos que pueda encontrar un algoritmo sustituto que no requiera tal almacenamiento de estado.

La recursión solo es más costosa si se desborda la pila. En cierto sentido, la iteración será más costosa (en esos algoritmos que se prestan a la recursión), porque estás recreando el mecanismo de almacenamiento de estado que ya ofrece la recursión.

    
respondido por el Robert Harvey 03.06.2014 - 17:13
2

Primero, si bien es cierto que siempre existe un equivalente iterativo equivalente a cualquier algoritmo recursivo, no es necesariamente el caso de que el equivalente iterativo sea mejor, para cualquier definición razonable de "mejor".

Para algunos algoritmos, el equivalente iterativo termina simulando el algoritmo recursivo, completo con parámetros simulados y apilamiento y desapilamiento de variables locales. Considere Función de Ackermann . Considere codificación Huffman . En estos casos, se gana muy poco al (re) escribir las operaciones explícitas de la pila.

Segundo, no es necesariamente el caso que la recursión sea siempre más costosa que la iteración. Considere recursión de la cola , y lea los documentos "Lambda: The Ultimate ...".

(Sí, sé que esto necesita una expansión. Tengo que ir a una cita con el médico en este momento).

    
respondido por el John R. Strohm 03.06.2014 - 18:55

Lea otras preguntas en las etiquetas