Diseños Recursivos Más Complejos

Hasta ahora todos los procedimientos recursivos mostraban la llamada recursiva como su instrucción final. Este tipo de recursión se llama recursión simple. Puede ser vista como una repetición general en la que las instrucciones se repiten para siempre.

Las recursiones más complejas tienen una o más instrucciones después de su línea recursiva. Un ejemplo simple consiste en modificar el procedimiento poliespi.

para cuaespiral :paso
si :paso > 50 [alto]
adelante :paso
derecha 90
cuaespiral :paso + 5
adelante :paso
izquierda 90
fin

Observe que se han puesto dos instrucciones después de la línea recursiva: adelante e izquierda.

cuaespiral 5

Para poder examinar el proceso, daremos a cuaespiral una entrada grande:

cuaespiral 40

Hay que tener en cuenta que cuando el subprocedimiento cuaespiral termina (cuando :paso es mayor que 50), el superprocedimiento no puede detenerse en forma inmediata. Cada subprocedimiento tiene que terminar de ejecutar sus instrucciones antes de poder parar. Cada cuaespiral mantiene su propio valor para :paso. Cada cuaespiral ejecuta adelante, con sus valores propios para :paso, y luego izquierda 90.

Un modelo acerca de cómo cuaespiral ejecuta sus instrucciones sería el siguiente:

Comienza cuaespiral 40; :paso es 40 1. si 40 > 50 [alto] ¿Es 40 > 50? Falso 2. adelante 40 3. derecha 90 4. cuaespiral 40 + 5
	Comienza cuaespiral 45; :paso es 45 1. si 45 > 50 [alto] ¿Es 45 > 50? Falso 2. adelante 45 3. derecha 90 4. cuaespiral 45 + 5
		Comienza cuaespiral 50; :paso es 50 1. si 50 > 50 [alto] ¿Es 50 > 50? Falso 2. adelante 50 3. derecha 90 4. cuaespiral 50 + 5
			Comienza cuaespiral 55; :paso es 55 1. si 55 > 50 [alto] ¿Es 55 > 50? Cierto Cuaespiral 55 se detiene.
		5. adelante 50 6. izquierda 90 Cuaespiral 50 se detiene.
	5. adelante 45 6. izquierda 90 Cuaespiral 45 se detiene.
5. adelante 40 6. izquierda 90 Cuaespiral 40 se detiene.

 

Este proceso nos lleva a la siguiente regla:

Cuando se llama a un procedimiento, el superprocedimiento espera hasta que termine el subprocedimiento, y luego continúa con la próxima instrucción.

Esta regla parece simple pero la situación se puede complicar cuando:

• Hay más de un llamado recursivo en el mismo procedimiento.
• Cada procedimiento recursivo tiene valores propios para sus entradas.
• Las cosas suceden en un orden inverso del que se espera. Esto se relaciona con el hecho de que el último procedimiento llamado es el primero en detenerse.

Un famoso ejemplo es el árbol binario (adaptado de Abelson, 1982). La descripción recursiva del árbol es una forma de V con un árbol más pequeño en cada punta. Cada uno de estos árboles más pequeños tiene a su vez forma de V con árboles más pequeños en sus puntas, y así sucesivamente. Por ejemplo:

Las instrucciones para dibujar cada forma de V en este árbol serían las siguientes: izquierda 45 adelante :largo atrás :largo derecha 90 adelante :largo atrás :largo izquierda 45

Supongamos que especificamos para nuestro árbol recursivo que cada árbol tenga en sus puntas otro árbol con la mitad de su tamaño. Para ello, el procedimiento árbol deberá llamarse a sí mismo después de cada adelante, con la mitad de su largo:

para árbol :largo
izquierda 45
adelante :largo
árbol :largo / 2
atrás :largo
derecha 90
adelante :largo
árbol :largo / 2 atrás :largo
izquierda 45
fin

Pero así el procedimiento no funcionará porque no hemos puesto una regla de detención. Cada árbol que se llame seguirá ejecutándose para siempre, sin nunca completar sus instrucciones. Una simple regla de detención hará que el árbol se detenga cuando :largo sea demasiado pequeño:

para árbol :largo
si :largo < 2 [alto]
izquierda 45
adelante :largo
árbol :largo / 2
atrás :largo
derecha 90
adelante :largo
árbol :largo / 2 atrás :largo
izquierda 45
fin

Pruebe ahora árbol.

árbol 40

Si usamos el modelo anterior, árbol 12 hará lo siguiente:

árbol 12 comienza; :largo es 12 1. si 12 < 2 [alto] ¿Es 12 < 2? Falso 2. izquierda 45 3. adelante 12 4. árbol 12 / 2
	árbol 6 comienza; :largo es 6 1. si 6 < 2 [alto] ¿Es 6 < 2? Falso 2. izquierda 45 3. adelante 6 4. árbol 6 / 2
		árbol 3 comienza; :largo es 3 1. si 3 < 2 [alto] ¿Es 3 < 2? Falso 2. izquierda 45 3. adelante 3 4. árbol 3 / 2
			árbol 1,5 comienza; :largo es 1,5 1. si 1,5 < 2 [alto] ¿Es 1,5 < 2? Cierto árbol 1,5 se detiene.
		5. atrás 3 6. derecha 90 7. adelante 3 8. árbol 3 / 2
			árbol 1,5 comienza; :largo es 1,5 1. si 1,5 < 2 [alto] árbol 1,5 se detiene.
		9. atrás 3 10. izquierda 45 árbol 3 se detiene.
	5. atrás 6 6. derecha 90 7. adelante 6 8. árbol 6 /2
		árbol 3 comienza; :largo es 3 1. si 3 < 2 [alto] ¿Es 3 < 2? Falso 2. izquierda 45 3. adelante 3 4. árbol 3 / 2
			árbol 1,5 comienza; :largo es 1,5 1. si 1,5 < 2 [alto] árbol 1,5 se detiene.
		5. atrás 3 6. derecha 90 7. adelante 3 8. árbol 3 / 2
			árbol 1,5 comienza; :largo es 1,5 1. si 1,5 < 2 [alto] árbol 1,5 se detiene.
		9. atrás 3 10. izquierda 45 árbol 3 se detiene.
	9. atrás 6 10. izquierda 45 árbol 6 se detiene.
5. atrás 12 6. derecha 90 7. adelante 12 8. árbol 12 / 2
	árbol 6 comienza; :largo es 6 1. si 6 < 2 [alto] ¿Es 6 < 2? Falso 2. izquierda 45 3. adelante 6 4. árbol 6 / 2
		árbol 3 comienza; :largo es 3 1. si 3 < 2 [alto] ¿Es 3 < 2? Falso 2. izquierda 45 3. adelante 3 4. árbol 3 / 2
			árbol 1,5 comienza; :largo es 1,5 1. si 1,5 < 2 [alto] árbol 1,5 se detiene.
		5. atrás 3 6. derecha 90 7. adelante 3 8. árbol 3 / 2
			árbol 1,5 comienza; :largo es 1,5 1. si 1,5 < 2 [alto] árbol 1,5 se detiene.
		9. atrás 3 10. izquierda 45 árbol 3 se detiene.
	5. atrás 6 6. derecha 90 7. adelante 6 8. árbol 6 / 2
		árbol 3 comienza; :largo es 3 1. si 3 < 2 [alto] ¿Es 3 < 2 ? Falso 2. izquierda 45 3. adelante 3 4. árbol 3 / 2
			árbol 1,5 comienza; :largo es 1,5 1. si 1,5 < 2 [alto] árbol 1,5 se detiene.
		5. atrás 3 6. derecha 90 7. adelante 3 8. árbol 3 / 2
			árbol 1,5 comienza; :largo es 1,5 1. si 1,5 < 2 [alto] árbol 1,5 se detiene.
		9. atrás 3 10. izquierda 45 árbol 3 se detiene.
	9. atrás 6 10. izquierda 45 árbol 6 se detiene.
9. atrás 12 10. izquierda 45 árbol 12 se detiene.

Pensar acerca de esta descripciones recursivas es difícil y requiere práctica. Sin embargo, merece la pena realizar el esfuerzo para poder sentirnos a gusto con este concepto. Las definiciones recursivas pueden ser concisas y elegantes. El procedimiento árbol parece muy simple, pero seguirlo a través de las diferentes ramas es sumamente complejo. En este árbol, es muy importante la transparencia del estado de la tortuga (el estado inicial y el final son iguales): los movimientos finales atrás e izquierda llevan a la tortuga a su posición y a su rumbo iniciales para que cada árbol tenga su par.