Algoritmos

INSTRUCCIONES: Para desarrollar el siguiente control, descargue desde la plataforma del curso la plantilla establecida por IACC para la entrega de controles de la semana, y realice las siguientes actividades.

1) Defina con sus propias palabras qué es un algoritmo recursivo y qué tipos de recursión existen.

2) Explique el algoritmo utilizado para resolver el juego-problema llamado “Las Torres de Hanoi”.

Desarrollo

1. Un algoritmo recursivo es una estructura que se llama a sí misma directa o indirectamente. La idea es que se llame las veces necesarias pero cada vez menos recursivas ya que no es la idea que sea un algoritmo recursivo infinito. Esto nos permite definir estructuras o programas complejos en términos de sí mismos.

• Recursividad directa: es la misma definida anteriormente como elemento recursivo que se llama a sí mismo.

• Recursividad indirecta: es cuando la función en vez de llamarse a si misma llama a otras y estas a su vez a la función de origen produciéndose una cadena.

Modos de recursión

• Recursión de cabeza: cuando la recursividad se produce al principio antes que cualquier proceso.

• Recursión de cola: cuando la llamada se hace al final de todas las operaciones.

• Recursión intermedia: junta los llamados antes y después de las operaciones.

• Recursión múltiple: es cuando se producen muchas llamadas en distintos sectores a lo largo del procedimiento.

• Recursión anidada: cuando la llamada se realiza desde un parámetro que es resultado de otra llamada recursiva.

2. Algoritmo “las Torres de Hanoi”

ORÍGEN= X CENTRAL= Y DETINO= Z

Si n = 1, lleva el disco 1 de X a Z y termina.

En otro caso:

Traslada la torre 1...n−1 usando este mismo algoritmo, de X a Y, usando como auxiliar Z.

Lleva el disco n de X a Z.

Traslada la torre 1...n−1 usando este mismo algoritmo, de Y a Z, usando como auxiliar X.

Bibliografía

IACC (s/f). Contenidos semana tres. En: Estructura de Datos. Semana 3. Santiago: IACC

IACC (s/f). Recurso 1 de semana tres. En: Estructura de Datos. Semana 2. Santiago: IACC

...