PDF de programación - Karel y Recuersión

Karel y Recursión

I. Entendiendo la Recursión

“Recursión es la forma en la cual se especifica un proceso basado en su propia definición. Siendo un 
poco más precisos, y para evitar el aparente círculo sin fin en esta definición, las instancias complejas 
de un proceso se definen en términos de instancias más simples, estando las finales más simples 
definidas de forma explícita.”

Wikipedia

La recursión es una herramienta muy poderosa en el uso de Karel.
La forma de aplicar la recursión en Karel es definiendo una instrucción en términos de sí misma. Si aún 
no queda del todo claro este concepto, muy posiblemente este ejemplo lo aclarará:

si junto­a­zumbador entonces
inicio

Código 1 – Ejemplo de Recursión
1 define nueva­instruccion coge­zumbadores como
2 inicio
3 
4 
5 
6 
7 
8 fin;

coge­zumbador;
coge­zumbadores;

fin;

No es muy dificil ver que lo que hace esta instrucción es tomar todos los zumbadores que hay en una 
casilla. En la línea 3 comprueba si hay zumbadores, si los hay, toma un zumbador (línea 5) y la función 
se llama a si misma (línea 6).
Volviendo a la definición formal de recursión, se dice que se definen las instancias complejas en 
términos de instancias mas simples, y las más simples de todas, definidas de forma explícita.
En el programa anterior se puede ver sin mucho problema que cada que se llama a la instrucción “coge­
zumbadores” hay un zumbador menos que la ultima vez que se llamó a la instrucción “coge­
zumbadores”, es decir, la instancia compleja (coge­zumbadores con x zumbadores en la casilla), se está 
definiendo en términos de una instancia mas simple(coge­zumbadores con x­1 zumbadores en la 
casilla). Y finalmente, si hay 0 zumbadores en la casilla, no realizará acción alguna, esto es, la instancia 
mas simple, definida explícitamente.
Podría estarse preguntado, ¿Qué sucede si alguna de estas condiciones no se cumplen pero la 
instruccion sigue definiendose en términos de sí misma?.
En caso de que eso suceda, la recursión pasaría a ser un bucle interminable.

Código 2 – Bucle infinito (falsa idea de recursión)
1 define nueva­instruccion bucle como
2 inicio
3 
4 fin;

bucle;

Si fuera posible seguir las especificaciones del lenguaje de Karel al pie de la letra, una vez llamada la 
función bucle el programa jamas terminaría.
Sin embargo, por cuestiones de memoria el programa en la practica si termina, pero no con una 
terminación normal, sino con un error llamado “desbordamiento de pila”.
Para entender a que se refiere con ésto, es necesario imaginar la memoria de la computadora donde 
Karel se está ejecutando.
Al llamar a una instrucción, obviamente Karel debe de “recordar” desde que línea fue llamado.
He aquí un ejemplo muy familiar:

Codigo 3 – Ejemplo de llamada a instrucción
1 iniciar­programa
2    define­nueva­instruccion gira­derecha como
3    inicio
4        repetir 3 veces
5            gira­izquierda;
6    fin;
7    inicia­ejecucion
8         deja­zumbador;
9         gira­derecha;
10        deja­zumbador;
11        apagate;
12    termina­ejecucion
13 finalizar­programa

Aquí, Karel inicia en la línea 7, deja un zumbador al llegar a la línea 8, y al llegar a la línea 9, se mueve 
súbitamente a la línea 4, repite 3 veces la línea 3. ¿Y luego qué?, salta a la línea 10, ¿por qué motivo?, 
obviamente porque la instrucción fue llamada desde la línea 9.
Para que Karel supiera a qué linea debía de ir despues de terminar de ejecutar “gira­derecha” necesitó 
recordarla, y eso implica ir guardando en algún lugar de la memoria la línea desde la cual se llamó a la 
instrucción actual.
Ahora, la pregunta obligatoria es ¿qué es lo que sucede cuando se llama a una instrucción dentro de 
otra instrucción?, obviamente no se puede olvidar desde dónde fue llamada la instrucción actual, y 
tambien es necesario recordar desde dónde se está llamando a la nueva instrucción, por lo tanto se 
tienen que guardar las 2 posiciones en memoria, cada que se llame a una instrucción dentro de otra, una 
nueva posición en memoria debe de guardar la línea desde la cual se este llamando a la instrucción.
Sin embargo, cuando una instrucción termina su ejecución, ya no es necesario seguir “recordando” 
desde donde se llamó a la instrucción.
De esa forma se puede saber que Karel guarda en memoria una especie de “lista” indicando desde 
donde fueron llamadas cada una de las instrucciones en el respectivo órden que fueron llamadas, cada 
que una instrucción nueva comienza su ejecución, un nuevo número se agrega al final de la “lista”, y 
cada que una instrucción termina su ejecución, un número se quita del final de la “lista”.
Bueno, pues a esta “lista” se le denomina pila o stack, la pila tiene un tamaño máximo, y si el programa 
sobrepasar este límite de memoria destinado a la pila, el programa súbitamente terminará.
Esto lleva a la pregunta: ¿Cuál es el tamaño máximo de pila de Karel? ¿es fijo o varía dependiendo de 
la computadora donde se ejecute?.

El tamaño máximo de la pila de Karel es fijo, y es exactamente de 5000 llamadas a instrucción 
anidadas, si alguien lo quiere comprobar, el siguiente código le será útil:

Código 4 – Soporte de Karel antes del desbordamiento de pila
1 define nueva­instruccion bucle como
2 inicio
3
4 
5 fin;

deja­zumabdor;
bucle;

Al ejecutarlo asegurese de tener suficientes zumbadores en la mochila, y verá como después de colocar 
5000 zumbadores el programa termina con el error de desbordamiento de pila.

II. Usando la Recursión en Karel para recuento

Si eres observador, seguramente te habrás dado cuenta que la recursión que se muestra en el código 1 es 
innecesaria e incluso puede causar un desbordamiento de pila si hay mas de 5000 zumbadores en la 
casilla que se está llamando.
Bien podría ser sustituido por esto:

Código 5 – Lo mismo que Código 1 pero eliminando la recursión
1 define nueva­instruccion coge­zumbadores como
2 inicio
3 
4
5 fin;

mientras junto­a­zumbador hacer

coge­zumbador;

Sin embargo, hay ocaciones en que la recursión resulta muy útil.
La principal utilidad de la recursión en Karel es la de realizar una operación luego de efectuar la 
llamada recursiva; un patrón general sería esta forma:

Pseudocódigo 1
define­nueva­instruccion (nombre­de­la­instruccion) como
inicio

(bloque­de­instrucciones­1)
(llamada­recursiva)
(bloque­de­instrucciones­2)

fin;

Aquí se entiende que en “llamada recursiva” ya está definida una condición que indica cuando dejará de 
llamarse la función a sí misma.
Si la función se llama a sí misma x veces, el bloque de instrucciones 1 se ejecutará x veces, y el bloque 
de instrucciones 2 tambien se ejecutará x veces después.
Nótese que este “patrón” NO tiene los mismos resultados que este otro:

Pseudocódigo 2
define­nueva­instruccion (nombre­de­la­instruccion) como
inicio

(bloque­de­instrucciones­1)
(bloque­de­instrucciones­2)
(llamada­recursiva)

fin;

En el pseudocódigo 2, tanto el bloque de instrucciones 1 como el bloque de instrucciones 2 se ejecutan 
mientras la condición para que la instrucción se siga llamando a sí misma sea verdadera.
Sin embargo, en el pseudocódigo 1, el bloque de instrucciones 1 se ejecuta mientras la condición para 
que la instruccion se llame a si misma sea verdadera, sin embargo, el bloque de instrucciones 2 se 
ejecuta por primera vez cuando dicha condición es falsa, y las siguientes veces se ejecuta 
independientemente de si la condición es verdadera o falsa. En esta propiedad radica el poder que tiene 
la recursión en Karel.

Problema de Ejemplo 1
Datos
Originalmente Karel se encuentra en la casilla (1, 1) orientado hacia el norte.
Karel tendrá infinitos zumbadores en la mochila.
En la posición 1, 1 habrá 0<=x<=99 zumbadores.
No habrá mas muros de los predeterminados en un mundo nuevo de Karel.
Problema
Escribe un programa que cuando termine su ejecución, Karel se encuentre en la casilla (1, x+1).

Solución
Una manera iterativa de hacerlo podría ser tener una columna de zumbadores en la avenida 1, e ir 
quintando un zumbadores de la casilla (1, 1) e irlos poniendo en la parte superior de la columna de uno 
por uno de tal forma que al final haya una columna de x zumbadores y Karel simplemente se deba 
colocar en la parte superior de la columna.
Sin embargo hay una solución mucho mas sencilla.
Karel puede tomar todos los zumbadores que haya en la casilla y luego por cada zumbador que tomó, 
avanzar un paso hacia delante.
Para hacer esto es necesario usar recursión.
El “bloque de instrucciones 1”, en este caso sería “coge­zumbador”, y el “bloque de instrucciones 2” 
sería “avanza”, Es decir, primero tomará todos los zumbadores y posteriormente avanzará tantas veces 
como zumbadores tomados.
El siguiente código resuelve este problema con la solución recursiva descrita

Código 6 – Solución al problema de ejemplo 1
1  iniciar­programa
2     define­nueva­instruccion funcion como
3     inicio
4         si junto­a­zumbador entonces
5         inicio
6             coge­zumbador;

7             funcion;
8             avanza;
9         fin;
10    fin;
11    inicia­ejecucion
12        funcion;
13        apagate;
14    termina­ejecucion
15 finalizar­programa

Si no te queda claro el funcionamiento del codigo anterior, es recomendable implementarlo y observar 
detenidamente cómo actua, pues es el problema mas básico y sencillo que se aborda en este tutorial.

Problema de Ejemplo 2
Datos
Originalmente Karel se encuentra en la casilla (1, 1) orientado hacia el este.
Hay un solo zumbador en el mundo, en la casilla (2x+1, 1).
No habrá mas muros de los predeterminados en un mundo nuevo de Karel.
Problema
Escribe un programa que cuando termine su ejecución, Karel se encuentre en la casilla (x+1, 1).

Solución
Aquí por cada par de pasos que Karel de al frente, deberá de dar un paso hacia atrás.
Una forma de lograr esto, sería asegurandose de que al dar un paso atrás, Karel siempre se encuentre 
orientado hacia el oeste y al dar 2 pasos para el frente, Karel siempre se encuentre orientado al este.
Sin embargo, una