Recursividad vs. iteración

Aspectos que hay que considerar al decidir cómo implementar la solución a un

problema (de forma iterativa o de forma recursiva):

- La carga computacional (tiempo de CPU y espacio en memoria) asociada a

las llamadas recursivas.

- La redundancia (algunas soluciones recursivas resuelven un problema en

repetidas ocasiones).

- La complejidad de la solución (en ocasiones, la solución iterativa es muy

difícil de encontrar).

- La concisión, legibilidad y elegancia del código resultante de la solución

recursiva del problema.

Algo recursivo o recurrente es algo que se llama a si mismo. Tiene que ver con el principio de inducción.

La recursividad consume muchísima memoria, ya que mantiene las variables del método mientras que se ejecuta, y también mucho tiempo. La recursividad es costosa pero es más natural, se prefiere. Por ejemplo, Java no puede implementar de forma recursiva el cálculo del factorial de un millón, pues cualquier computador se quedaría sin memoria, sin embargo, es necesario de implementar para poder escribir y entender ciertos programas.

Recursividad vs. Iteración

1- Ambas realizan una repetición:

a)Solución iterativa repite el cuerpo del bucle.

b)Solución recursiva repite las llamadas al método recursivo.

2- Ambas tienen una condición de terminación.

a)Solución iterativa: termina cuando se imcumple la condición de continuación del bucle.

b)Solución recursiva: se termina cuando una llamada alcanza el caso base (inducción) desencadenando una secuencia de vuelta atrás.

Backtracking: sucesión de pruebas tentativas.

3- Ambas se deben diseñar para converger a la solución (principio de convergencia, y que no se salten la condición de terminación).

a)Solución iterativa: se llega a cumplir la condición de terminación (esto se debe garantizar).

b)Solución recursiva: se debe garantizar que se llegue al caso base.

Principio importante: Toda solución recursiva puede encontrar una solución iterativa equivalente, mientras que lo contrario no siempre es cierto.

 

aqui un pequeño ejemplo con un simulador de las torres de hanoi

aqui tienen una pequeña parte del codigo recursivo del simulador del video

y aqui una pequeña parte del codigo iterativo

y aqui el link de descarga por si quieren probrar este simulador

http://www.megaupload.com/?d=AXRI1TTR