This lesson continues 8 Basic Concepts of Programming in TLAC. You only need the ideas of a variable, a condition, a function, and a loop. We will use plain-language instruction cards to learn two new ideas.
Recursion: a function calls itself to continue a job.
Classes: describe a kind of object, with its own information and actions.
Problems 4–8 below keep the original programs’ order and decisions. They are board-game examples for their intended starting positions and board layouts, not general maze solvers. An egg marks a visited square. A move of 2 uses the destination two spaces ahead; these examples assume clear paths.
After each program, compare its initial and final boards, then open the full execution link. Use Next and Previous to follow every instruction, action, and function return, or expand all steps to see every board together. The numbered instructions match the program cards. The turtle picture hides an egg directly underneath it; the egg count still includes that egg.
1. First, without recursion
Start with repetition you already know: a loop. Read all five non-recursive examples first. For each, ask: what repeats, what changes, and what makes it stop? Then compare them with the recursive versions in the next section.
Problem 4 · Follow a route, one space at a time
Turn left once. Each time around the loop, first look for an egg under the turtle. If there is one, end the program. Otherwise, turn right if the way ahead is blocked, place an egg, and move one space. The next loop checks the new square.
This is the same loop pattern as problem 4, but both the movement check and the movement use a distance of 2. Eggs are placed only on the squares where the turtle stands, not on the skipped squares. The stop rule is still finding an egg underneath.
Without recursion · Problem 5
0001
Problem 5
0002
Initial action before the loop
0003
Function call: Turn Turtle Left
0004
0005
Repeat until an instruction stops this loop
0006
Check when to stop
0007
If the turtle is standing on an egg, then
0008
Function call: End Program
0009
Leave the innermost loop
0010
0011
Turtle actions
0012
Use distance 2 for both the check and the movement
Problem 6 · Fill lines, then move to the next line
There are several jobs: reach a wall, fill one line with eggs, then turn and move to the next line. Small inner loops move along a line; the large outer loop repeats the board pattern. Place one final egg when the end of a line is reached.
Problem 7 · Fill on the upward pass, travel on the return
After the initial line is filled, the outer loop checks the direction. Facing up, it fills a line with eggs. On the downward pass, it moves board height − 1 spaces without placing eggs. It then turns toward the next column. On an empty board, that distance goes from one end of a column to the other.
First go to the top-left corner, face down, and move down one square. The inner loop places eggs every 2 spaces down or up a column. The outer loop moves across 2 columns and repeats. At the right edge, it checks whether one final sideways step is possible, adjusts the position if so, and ends.
Without recursion · Problem 8
0001
Main instructions: start here
0002
0003
Step A: Go to the left wall (column 0)
0004
Function call: Turn Turtle Left
0005
While the turtle can move forward 1 space, repeat
0006
Function call: Move Turtle Forward 1 space
0007
0008
Step B: Face up and go to the top wall (row 0)
0009
Function call: Turn Turtle Right
0010
While the turtle can move forward 1 space, repeat
0011
Function call: Move Turtle Forward 1 space
0012
0013
Step C: Turn around, face down, and move 1 space to row 1
0014
Function call: Turn Turtle Right
0015
Function call: Turn Turtle Right
0016
Function call: Move Turtle Forward 1 space
0017
0018
Step D: Start the winding route with a loop
0019
Repeat until an instruction stops this loop
0020
1. Place eggs along this column
0021
While the turtle can move forward 2 spaces, repeat
0022
Function call: Place an egg under the turtle
0023
Function call: Move Turtle Forward — distance: 2
0024
Function call: Place the last egg in this column
0025
0026
2. Move to the next column or stop
0027
When the turtle reaches the top facing up
0028
If the turtle is facing up, then
0029
Function call: Turn Turtle Right
0030
Check whether the right edge is too close for 2 spaces
0031
If the turtle cannot move forward 2 spaces, then
0032
If the turtle can move forward 1 space, then
0033
Function call: Move Turtle Forward 1 space
0034
Function call: Turn Turtle Right
0035
Function call: End Program
0036
Leave the innermost loop
0037
0038
Function call: Move Turtle Forward — distance: 2
0039
Function call: Turn Turtle Right
0040
0041
When the turtle reaches the bottom facing down
0042
Otherwise
0043
Function call: Turn Turtle Left
0044
Check whether the right edge is too close for 2 spaces
0045
If the turtle cannot move forward 2 spaces, then
0046
Adjust the final corner position if one more space is available
A loop says “do these instructions again.” A recursive function says “do one part, then call this same function for what remains.” Every safe recursive process needs a stopping case (often called the base case) and progress toward that case. The smaller job might be a shorter distance to a wall or fewer unvisited squares.
A definition does not move the turtle. It gives a group of instructions a name. In these recursive charts, begin with the main instructions after the function definitions. A call enters the named function. A call from inside that same function is recursion. Calling a different helper function is an ordinary function call.
Follow the calls: two spaces from a wall
Imagine goToBeginningOfBoard starting two spaces from the wall. Each call keeps a bookmark saying where to continue when its helper finishes. A new call uses the same instructions, but the turtle’s position has already changed.
Call A: 2 spaces remain → move 1 space → call B; A waits.
Call B: 1 space remains → move 1 space → call C; B waits.
Call C: at the wall → cannot move → return to B. This is the base case.
B has nothing left to do → return to A. A also finishes → return to the main instructions.
These waiting calls form a call stack: the last call started is the first to finish. Returning does not undo a move; the turtle stays at the wall. For the board game, put each return bookmark on a small pile of paper slips, and remove the top slip when returning.
Function-name guide
P
one step of the route
goToBeginningOfBoard
go to the wall ahead
fillThisRowWithEggs
fill this line with eggs
fillThisColumnWithEggs
place eggs every two spaces in this column
repeatThisUntilBoardFull
repeat the board pattern
Problem 4 · Follow a route, one space at a time
P contains one pass through the same actions. Its last instruction calls P again, now with the turtle on a new square. The call inside P is the recursive call. The stopping case is standing on an egg; End Program stops the entire run.
With recursion · Problem 4
0001
Problem 4
0002
Function definition: P
0003
If the turtle is standing on an egg, then
0004
Function call: End Program
0005
If the turtle cannot move forward 1 space, then
0006
Function call: Turn Turtle Right
0007
Function call: Place an egg under the turtle
0008
Function call: Move Turtle Forward 1 space
0009
Function call: P
0010
Function call: Turn Turtle Left
0011
Function call: P
Find the egg check before the next move. Without it, returning to a visited square would not stop the route.
P again calls itself after moving. The repeated action now advances 2 spaces, but the recursive structure has not changed. A distance check of 1 would not establish that a move of 2 stays on the board.
With recursion · Problem 5
0001
Problem 5
0002
Function definition: P
0003
If the turtle is standing on an egg, then
0004
Function call: End Program
0005
If the turtle cannot move forward 2 spaces, then
0006
Function call: Turn Turtle Right
0007
Function call: Place an egg under the turtle
0008
Function call: Move Turtle Forward — distance: 2
0009
Function call: P
0010
Function call: Turn Turtle Left
0011
Function call: P
Compare the two distance values. They must describe the same intended move.
Problem 6 · Fill lines, then move to the next line
Three named functions take over those jobs. goToBeginningOfBoard moves and calls itself until it reaches a wall. fillThisRowWithEggs places eggs and calls itself until the line ends, then places the last egg and returns. repeatThisUntilBoardFull calls the filling function, changes lines, and calls itself again until End Program is reached.
With recursion · Problem 6
0001
Problem 6
0002
Function definition: goToBeginningOfBoard
0003
If the turtle can move forward 1 space, then
0004
Function call: Move Turtle Forward 1 space
0005
Function call: goToBeginningOfBoard
0006
Otherwise
0007
Return to the instruction after the call
0008
Function definition: fillThisRowWithEggs
0009
If the turtle can move forward 1 space, then
0010
Function call: Place an egg under the turtle
0011
Function call: Move Turtle Forward 1 space
0012
Function call: fillThisRowWithEggs
0013
Otherwise
0014
Function call: Place an egg under the turtle
0015
Return to the instruction after the call
0016
Function definition: repeatThisUntilBoardFull
0017
Function call: fillThisRowWithEggs
0018
If the turtle is facing up, then
0019
Function call: Turn Turtle Right
0020
Function call: Move Turtle Forward 1 space
0021
Function call: Turn Turtle Right
0022
Otherwise
0023
Function call: Turn Turtle Left
0024
If the turtle is facing right, then
0025
If the turtle cannot move forward 1 space, then
0026
Function call: End Program
0027
Function call: Move Turtle Forward 1 space
0028
Function call: Turn Turtle Left
0029
Function call: repeatThisUntilBoardFull
0030
Function call: Turn Turtle Left
0031
Function call: goToBeginningOfBoard
0032
Function call: Turn Turtle Right
0033
Function call: fillThisRowWithEggs
0034
Function call: repeatThisUntilBoardFull
These supplied examples fill the first line before the main repetition and visit its final square again at the start of that repetition. In TLAC, placing an egg marks a square as occupied; it does not stack another egg there. The function name says “Row”, but the turtle travels vertically here, along a column.
Problem 7 · Fill on the upward pass, travel on the return
The outer function still calls itself, but its direction check chooses which work to do first. The upward branch calls fillThisRowWithEggs; the other branch makes the long move. The filling helper returns at the wall, while the overall pattern ends at the right-edge check.
fillThisColumnWithEggs calls itself after each 2-space move. Its stopping case places the final egg and returns when another 2-space move is impossible. repeatThisUntilBoardFull handles the turns and calls itself for the next column. If moving across 2 columns is impossible, the program ends instead of making another recursive call.
With recursion · Problem 8
0001
1. Move the turtle to the wall ahead
0002
Function definition: goToBeginningOfBoard
0003
If the turtle can move forward 1 space, then
0004
Function call: Move Turtle Forward 1 space
0005
Function call: goToBeginningOfBoard
0006
Otherwise
0007
Return to the instruction after the call
0008
0009
2. Place an egg, move 2 spaces, and call this function again
0010
Function definition: fillThisColumnWithEggs
0011
If the turtle can move forward 2 spaces, then
0012
Function call: Place an egg under the turtle
0013
Function call: Move Turtle Forward — distance: 2
0014
Function call: fillThisColumnWithEggs
0015
Otherwise
0016
Function call: Place an egg under the turtle
0017
Return to the instruction after the call
0018
0019
3. Turn, move across 2 columns, and repeat
0020
Function definition: repeatThisUntilBoardFull
0021
Function call: fillThisColumnWithEggs
0022
0023
When the turtle reaches the top facing up
0024
If the turtle is facing up, then
0025
Function call: Turn Turtle Right
0026
Check whether the right edge is too close for 2 spaces
0027
If the turtle cannot move forward 2 spaces, then
0028
If the turtle can move forward 1 space, then
0029
Function call: Move Turtle Forward 1 space
0030
Function call: Turn Turtle Right
0031
Function call: End Program
0032
Return to the instruction after the call
0033
0034
Function call: Move Turtle Forward — distance: 2
0035
Function call: Turn Turtle Right
0036
0037
When the turtle reaches the bottom facing down
0038
Otherwise
0039
Function call: Turn Turtle Left
0040
Check whether the right edge is too close for 2 spaces
0041
If the turtle cannot move forward 2 spaces, then
0042
Adjust the final corner position if one more space is available
0043
If the turtle can move forward 1 space, then
0044
Function call: Move Turtle Forward 1 space
0045
Function call: Turn Turtle Right
0046
Function call: End Program
0047
Return to the instruction after the call
0048
0049
Function call: Move Turtle Forward — distance: 2
0050
Function call: Turn Turtle Left
0051
0052
Call this function again for the new column
0053
Function call: repeatThisUntilBoardFull
0054
0055
0056
Main instructions: start here
0057
0058
Step A: Go to the left wall (column 0)
0059
Function call: Turn Turtle Left
0060
Function call: goToBeginningOfBoard
0061
0062
Step B: Face up and go to the top wall (row 0)
0063
Function call: Turn Turtle Right
0064
Function call: goToBeginningOfBoard
0065
0066
Step C: Turn around, face down, and move 1 space to row 1
0067
Function call: Turn Turtle Right
0068
Function call: Turn Turtle Right
0069
Function call: Move Turtle Forward 1 space
0070
0071
Step D: Start the winding route with recursive calls
0072
Function call: repeatThisUntilBoardFull
There are two different stopping questions: “Can I continue this column?” and “Can I reach another column?” Each repeated job needs its own answer.
Which should you choose? For a simple repeated movement, a loop is often easier to follow. Recursion is useful when the remaining work naturally resembles the original job. Each unfinished call needs a return bookmark, so very deep recursion can use too much memory. These examples teach the idea; recursion does not automatically make a program faster.
3. Classes and objects
A class describes a kind of thing: the information it keeps and the actions it can perform. Here our class describes a turtle. An object is one particular turtle made from that description, also called an instance. Aki and Sol can be two objects of the same Turtle class.
Class: Turtle
Attributes (stored information): name, horizontal position X, vertical position Y, and direction.
Constructor (initial setup): receive a name and starting X and Y; create this turtle there, facing up.
Method “Move forward”: move this turtle one square in its own direction.
Method “Turn right”: rotate this turtle 90° clockwise; its position stays the same.
Method “Place an egg”: place an egg on this turtle’s current square.
Method “Mark and move”: ask this turtle to place an egg, then ask it to move forward. One method can use other methods.
An attribute is a named piece of information belonging to an object. A method is a function provided by its class. “This turtle” means the object receiving the request: asking Aki to move changes Aki’s position. The class definition alone does not create a turtle or move it. Creating an object runs its constructor, not all of its methods.
These examples use a 6 × 6 TLAC board. X increases to the right; Y increases downward. The top-left square is X=0, Y=0. The paths below stay inside the board. The full executions show every method request and the individual turtle actions it causes.
Example 1: one turtle leaves an egg trail
Create Aki at X=1, Y=4, facing up. Ask Aki to mark and move twice, turn right, and mark and move once more. The two upward moves change Y from 4 to 2. The final move changes X from 1 to 2. Aki finishes at X=2, Y=2, facing right, with three eggs left behind.
Start a fresh board. Create Aki at X=1, Y=4 and Sol at X=4, Y=4. Both face up. Ask Aki to mark and move twice. Sol has not moved! Now ask Sol to turn right and mark and move once. Aki stays at X=1, Y=2, facing up; Sol finishes at X=5, Y=4, facing right.
Same class, separate state. Aki and Sol use the same methods, but each stores its own name, X, Y, and direction. They share the board, so both can see eggs placed on it. An egg belongs to a board square, not to the turtle’s personal attributes. The execution page lists both turtles’ states so you can see which one changes.
Calling “Mark and move” uses other methods, but it is not recursion: that method never calls itself. Classes organize information and actions. Recursion is a way for a function to repeat work. A method can be recursive, but it does not have to be.
4. Try it yourself
1. What if the move toward the wall is removed?
Show an answer
If the turtle starts away from the wall, the next call sees the same position. It keeps calling without reaching the base case. A stopping condition alone is not enough: the repeated action must make progress.
2. Does returning from the column-filling function end the entire program?
Show an answer
No. Return resumes the caller. That caller may turn the turtle and start another column. End Program is the instruction that stops everything.
3. Aki and Sol face up. Ask only Sol to turn right. Does Aki turn too?
Show an answer
No. Sol faces right; Aki still faces up. Each turtle object stores its own direction attribute.
4. Design a “Turn around” method for the Turtle class.
Show an answer
Ask this turtle to turn right twice. Its direction changes by 180°, while X and Y stay unchanged. Another turtle on the board should keep its own direction.
Remember: recursion needs a stopping case and progress toward it. A class describes attributes and methods; each object has its own state. You can trace both ideas with paper, coins, and a few instruction cards.
Esta lección continúa 8 conceptos básicos de programación en TLAC. Solo necesitas las ideas de variable, condición, función y bucle. Usaremos tarjetas de instrucciones en lenguaje sencillo para aprender dos ideas nuevas.
Recursión: una función se llama a sí misma para continuar una tarea.
Clases: describen un tipo de objeto, con su propia información y sus acciones.
Los problemas 4–8 conservan el orden y las decisiones de los programas originales. Son ejemplos para sus posiciones iniciales y tableros previstos, no soluciones para cualquier laberinto. Un huevo marca una casilla visitada. Un movimiento de 2 usa la casilla de destino situada a dos pasos; estos ejemplos suponen caminos despejados.
Después de cada programa, compara sus tableros inicial y final y abre el enlace a la ejecución completa. Usa Siguiente y Anterior para seguir cada instrucción, acción y retorno de función, o despliega todos los pasos para ver todos los tableros juntos. Los números coinciden con las tarjetas del programa. La imagen de la tortuga oculta el huevo que hay justo debajo; el recuento sí lo incluye.
1. Primero, sin recursión
Empieza con una repetición que ya conoces: un bucle. Lee primero los cinco ejemplos sin recursión. En cada uno, pregunta: ¿qué se repite, qué cambia y qué lo detiene? Después compáralos con las versiones recursivas de la siguiente sección.
Problema 4 · Seguir un recorrido, una casilla a la vez
Gira a la izquierda una vez. En cada vuelta del bucle, primero comprueba si hay un huevo debajo de la tortuga. Si lo hay, termina el programa. Si no, gira a la derecha si no puedes avanzar, pon un huevo y avanza una casilla. La siguiente vuelta comprueba la nueva casilla.
Sin recursión · Problema 4
0001
Problema 4 — sin recursión
0002
Acción inicial antes del bucle
0003
Llamar a la función: Girar la tortuga a la izquierda
0004
0005
Repetir hasta que una instrucción detenga este bucle
0006
Comprobar cuándo parar
0007
Si la tortuga está sobre un huevo, entonces
0008
Llamar a la función: Terminar programa
0009
Salir del bucle más interno
0010
0011
Acciones de la tortuga
0012
Si la tortuga no puede avanzar 1 casilla, entonces
0013
Llamar a la función: Girar la tortuga a la derecha
0014
0015
Llamar a la función: Poner un huevo debajo de la tortuga
Es el mismo patrón de bucle del problema 4, pero tanto la comprobación como el movimiento usan una distancia de 2. Los huevos se ponen solo en las casillas donde está la tortuga, no en las que salta. La regla de parada sigue siendo encontrar un huevo debajo.
Sin recursión · Problema 5
0001
Problema 5
0002
Acción inicial antes del bucle
0003
Llamar a la función: Girar la tortuga a la izquierda
0004
0005
Repetir hasta que una instrucción detenga este bucle
0006
Comprobar cuándo parar
0007
Si la tortuga está sobre un huevo, entonces
0008
Llamar a la función: Terminar programa
0009
Salir del bucle más interno
0010
0011
Acciones de la tortuga
0012
Usar la distancia 2 tanto al comprobar como al avanzar
0013
Si la tortuga no puede avanzar 2 casillas, entonces
0014
Llamar a la función: Girar la tortuga a la derecha
0015
0016
Llamar a la función: Poner un huevo debajo de la tortuga
0017
Llamar a la función: Avanzar la tortuga — distancia: 2
Hay varias tareas: llegar a una pared, llenar una línea de huevos y luego girar y pasar a la siguiente. Los bucles interiores recorren una línea; el bucle exterior repite el patrón del tablero. Al llegar al final de una línea, se pone un último huevo.
Sin recursión · Problema 6
0001
Problema 6
0002
1. Girar a la izquierda e ir hasta la pared
0003
Llamar a la función: Girar la tortuga a la izquierda
0004
Mientras la tortuga pueda avanzar 1 casilla, repetir
0005
Llamar a la función: Avanzar la tortuga 1 casilla
0006
Llamar a la función: Girar la tortuga a la derecha
0007
0008
2. Llenar la primera línea antes del bucle principal
0009
Mientras la tortuga pueda avanzar 1 casilla, repetir
0010
Llamar a la función: Poner un huevo debajo de la tortuga
0011
Llamar a la función: Avanzar la tortuga 1 casilla
0012
Llamar a la función: Poner un huevo debajo de la tortuga
0013
0014
3. Bucle principal para el resto del tablero
0015
Repetir hasta que una instrucción detenga este bucle
0016
Bucle interior: llenar esta línea de huevos
0017
Mientras la tortuga pueda avanzar 1 casilla, repetir
0018
Llamar a la función: Poner un huevo debajo de la tortuga
0019
Llamar a la función: Avanzar la tortuga 1 casilla
0020
Llamar a la función: Poner un huevo debajo de la tortuga
0021
0022
Girar y avanzar a la siguiente línea
0023
Si la tortuga mira hacia arriba, entonces
0024
Llamar a la función: Girar la tortuga a la derecha
0025
Llamar a la función: Avanzar la tortuga 1 casilla
0026
Llamar a la función: Girar la tortuga a la derecha
0027
En caso contrario
0028
Llamar a la función: Girar la tortuga a la izquierda
0029
Comprobar si hemos llegado al borde del tablero
0030
Si la tortuga mira hacia la derecha, entonces
0031
Si la tortuga no puede avanzar 1 casilla, entonces
0032
Llamar a la función: Terminar programa
0033
Salir del bucle más interno
0034
0035
Llamar a la función: Avanzar la tortuga 1 casilla
0036
Llamar a la función: Girar la tortuga a la izquierda
Problema 7 · Llenar al subir y desplazarse al bajar
Después de llenar la primera línea, el bucle exterior comprueba la dirección. Al mirar hacia arriba, llena una línea de huevos. Al bajar, avanza la altura del tablero − 1 sin poner huevos. Después gira hacia la siguiente columna. En un tablero vacío, esa distancia recorre una columna de un extremo al otro.
Sin recursión · Problema 7
0001
Problema 7
0002
Llamar a la función: Girar la tortuga a la izquierda
0003
0004
1. Ir hasta la pared de enfrente
0005
Mientras la tortuga pueda avanzar 1 casilla, repetir
0006
Llamar a la función: Avanzar la tortuga 1 casilla
0007
0008
Llamar a la función: Girar la tortuga a la derecha
0009
0010
2. Llenar la primera línea de huevos
0011
Mientras la tortuga pueda avanzar 1 casilla, repetir
0012
Llamar a la función: Poner un huevo debajo de la tortuga
0013
Llamar a la función: Avanzar la tortuga 1 casilla
0014
Llamar a la función: Poner un huevo debajo de la tortuga
0015
0016
3. Repetir el patrón del tablero
0017
Repetir hasta que una instrucción detenga este bucle
0018
Si la tortuga mira hacia arriba, entonces
0019
Llenar esta línea de huevos aquí
0020
Mientras la tortuga pueda avanzar 1 casilla, repetir
0021
Llamar a la función: Poner un huevo debajo de la tortuga
0022
Llamar a la función: Avanzar la tortuga 1 casilla
0023
Llamar a la función: Poner un huevo debajo de la tortuga
0024
0025
Girar después de avanzar hacia arriba
0026
Llamar a la función: Girar la tortuga a la derecha
0027
Llamar a la función: Avanzar la tortuga 1 casilla
0028
Llamar a la función: Girar la tortuga a la derecha
0029
En caso contrario
0030
Avanzar la altura del tablero menos 1
0031
Llamar a la función: Avanzar la tortuga — distancia: altura del tablero − 1
0032
Llamar a la función: Girar la tortuga a la izquierda
0033
0034
Comprobar cuándo parar
0035
Si la tortuga mira hacia la derecha, entonces
0036
Si la tortuga no puede avanzar 1 casilla, entonces
0037
Llamar a la función: Terminar programa
0038
Salir del bucle más interno
0039
0040
Llamar a la función: Avanzar la tortuga 1 casilla
0041
Llamar a la función: Girar la tortuga a la izquierda
Primero ve a la esquina superior izquierda, mira hacia abajo y baja una casilla. El bucle interior pone huevos cada 2 casillas al subir o bajar por una columna. El bucle exterior avanza 2 columnas y repite. En el borde derecho, comprueba si cabe un último paso lateral, ajusta la posición si es posible y termina.
Sin recursión · Problema 8
0001
Instrucciones principales: empezar aquí
0002
0003
Paso A: Ir a la pared izquierda (columna 0)
0004
Llamar a la función: Girar la tortuga a la izquierda
0005
Mientras la tortuga pueda avanzar 1 casilla, repetir
0006
Llamar a la función: Avanzar la tortuga 1 casilla
0007
0008
Paso B: Mirar hacia arriba e ir a la pared superior (fila 0)
0009
Llamar a la función: Girar la tortuga a la derecha
0010
Mientras la tortuga pueda avanzar 1 casilla, repetir
0011
Llamar a la función: Avanzar la tortuga 1 casilla
0012
0013
Paso C: Dar media vuelta, mirar hacia abajo y avanzar 1 casilla hasta la fila 1
0014
Llamar a la función: Girar la tortuga a la derecha
0015
Llamar a la función: Girar la tortuga a la derecha
0016
Llamar a la función: Avanzar la tortuga 1 casilla
0017
0018
Paso D: Iniciar el recorrido de ida y vuelta con un bucle
0019
Repetir hasta que una instrucción detenga este bucle
0020
1. Poner huevos a lo largo de esta columna
0021
Mientras la tortuga pueda avanzar 2 casillas, repetir
0022
Llamar a la función: Poner un huevo debajo de la tortuga
0023
Llamar a la función: Avanzar la tortuga — distancia: 2
0024
Llamar a la función: Poner el último huevo de esta columna
0025
0026
2. Pasar a la siguiente columna o parar
0027
Cuando la tortuga llega arriba mirando hacia arriba
0028
Si la tortuga mira hacia arriba, entonces
0029
Llamar a la función: Girar la tortuga a la derecha
0030
Comprobar si el borde derecho está demasiado cerca para avanzar 2 casillas
0031
Si la tortuga no puede avanzar 2 casillas, entonces
0032
Si la tortuga puede avanzar 1 casilla, entonces
0033
Llamar a la función: Avanzar la tortuga 1 casilla
0034
Llamar a la función: Girar la tortuga a la derecha
0035
Llamar a la función: Terminar programa
0036
Salir del bucle más interno
0037
0038
Llamar a la función: Avanzar la tortuga — distancia: 2
0039
Llamar a la función: Girar la tortuga a la derecha
0040
0041
Cuando la tortuga llega abajo mirando hacia abajo
0042
En caso contrario
0043
Llamar a la función: Girar la tortuga a la izquierda
0044
Comprobar si el borde derecho está demasiado cerca para avanzar 2 casillas
0045
Si la tortuga no puede avanzar 2 casillas, entonces
0046
Ajustar la posición final en la esquina si queda una casilla
0047
Si la tortuga puede avanzar 1 casilla, entonces
0048
Llamar a la función: Avanzar la tortuga 1 casilla
0049
Llamar a la función: Girar la tortuga a la derecha
0050
Llamar a la función: Terminar programa
0051
Salir del bucle más interno
0052
0053
Llamar a la función: Avanzar la tortuga — distancia: 2
0054
Llamar a la función: Girar la tortuga a la izquierda
Un bucle dice «haz estas instrucciones otra vez». Una función recursiva dice «haz una parte y llama a esta misma función para lo que falta». Todo proceso recursivo que deba terminar necesita un caso de parada (o caso base) y avanzar hacia él. La tarea restante puede ser una distancia menor hasta una pared o menos casillas sin visitar.
Una definición no mueve la tortuga. Da un nombre a un grupo de instrucciones. En estas tarjetas recursivas, empieza por las instrucciones principales que vienen después de las definiciones. Una llamada entra en la función indicada. Si una función se llama a sí misma, hay recursión. Llamar a otra función auxiliar es una llamada normal.
Sigue las llamadas: a dos casillas de una pared
Imagina que goToBeginningOfBoard empieza a dos casillas de la pared. Cada llamada guarda un marcador que indica dónde continuar cuando termine la llamada que hace. La nueva llamada usa las mismas instrucciones, pero la posición de la tortuga ya ha cambiado.
Llamada A: faltan 2 casillas → avanzar 1 → llamar a B; A espera.
Llamada B: falta 1 casilla → avanzar 1 → llamar a C; B espera.
Llamada C: está en la pared → no puede avanzar → volver a B. Este es el caso base.
A B no le queda nada por hacer → vuelve a A. A también termina → vuelve a las instrucciones principales.
Estas llamadas en espera forman una pila de llamadas: la última que empieza es la primera que termina. Volver no deshace los movimientos; la tortuga se queda en la pared. Para jugar en papel, apila papelitos con el lugar al que debes volver y retira el de arriba al regresar.
Guía de nombres de funciones
P
un paso del recorrido
goToBeginningOfBoard
ir hasta la pared de enfrente
fillThisRowWithEggs
llenar esta línea de huevos
fillThisColumnWithEggs
poner huevos cada dos casillas en esta columna
repeatThisUntilBoardFull
repetir el patrón del tablero
Problema 4 · Seguir un recorrido, una casilla a la vez
P contiene una vuelta de las mismas acciones. Su última instrucción vuelve a llamar a P, ahora con la tortuga en otra casilla. La llamada dentro de P es la llamada recursiva. El caso de parada es estar sobre un huevo; Terminar programa detiene toda la ejecución.
Con recursión · Problema 4
0001
Problema 4
0002
Definir la función: P
0003
Si la tortuga está sobre un huevo, entonces
0004
Llamar a la función: Terminar programa
0005
Si la tortuga no puede avanzar 1 casilla, entonces
0006
Llamar a la función: Girar la tortuga a la derecha
0007
Llamar a la función: Poner un huevo debajo de la tortuga
0008
Llamar a la función: Avanzar la tortuga 1 casilla
0009
Llamar a la función: P
0010
Llamar a la función: Girar la tortuga a la izquierda
0011
Llamar a la función: P
Busca la comprobación del huevo antes del siguiente movimiento. Sin ella, volver a una casilla visitada no detendría el recorrido.
P vuelve a llamarse después de avanzar. La acción repetida ahora avanza 2 casillas, pero la estructura recursiva no cambia. Comprobar una distancia de 1 no bastaría para saber si un movimiento de 2 permanece dentro del tablero.
Con recursión · Problema 5
0001
Problema 5
0002
Definir la función: P
0003
Si la tortuga está sobre un huevo, entonces
0004
Llamar a la función: Terminar programa
0005
Si la tortuga no puede avanzar 2 casillas, entonces
0006
Llamar a la función: Girar la tortuga a la derecha
0007
Llamar a la función: Poner un huevo debajo de la tortuga
0008
Llamar a la función: Avanzar la tortuga — distancia: 2
0009
Llamar a la función: P
0010
Llamar a la función: Girar la tortuga a la izquierda
0011
Llamar a la función: P
Compara las dos distancias. Deben describir el mismo movimiento previsto.
Tres funciones con nombre se encargan de esas tareas. goToBeginningOfBoard avanza y se llama hasta llegar a una pared. fillThisRowWithEggs pone huevos y se llama hasta el final de la línea; allí pone el último huevo y vuelve. repeatThisUntilBoardFull llama a la función de llenado, cambia de línea y se llama de nuevo hasta llegar a Terminar programa.
Con recursión · Problema 6
0001
Problema 6
0002
Definir la función: goToBeginningOfBoard
0003
Si la tortuga puede avanzar 1 casilla, entonces
0004
Llamar a la función: Avanzar la tortuga 1 casilla
0005
Llamar a la función: goToBeginningOfBoard
0006
En caso contrario
0007
Volver a la instrucción que sigue a la llamada
0008
Definir la función: fillThisRowWithEggs
0009
Si la tortuga puede avanzar 1 casilla, entonces
0010
Llamar a la función: Poner un huevo debajo de la tortuga
0011
Llamar a la función: Avanzar la tortuga 1 casilla
0012
Llamar a la función: fillThisRowWithEggs
0013
En caso contrario
0014
Llamar a la función: Poner un huevo debajo de la tortuga
0015
Volver a la instrucción que sigue a la llamada
0016
Definir la función: repeatThisUntilBoardFull
0017
Llamar a la función: fillThisRowWithEggs
0018
Si la tortuga mira hacia arriba, entonces
0019
Llamar a la función: Girar la tortuga a la derecha
0020
Llamar a la función: Avanzar la tortuga 1 casilla
0021
Llamar a la función: Girar la tortuga a la derecha
0022
En caso contrario
0023
Llamar a la función: Girar la tortuga a la izquierda
0024
Si la tortuga mira hacia la derecha, entonces
0025
Si la tortuga no puede avanzar 1 casilla, entonces
0026
Llamar a la función: Terminar programa
0027
Llamar a la función: Avanzar la tortuga 1 casilla
0028
Llamar a la función: Girar la tortuga a la izquierda
0029
Llamar a la función: repeatThisUntilBoardFull
0030
Llamar a la función: Girar la tortuga a la izquierda
0031
Llamar a la función: goToBeginningOfBoard
0032
Llamar a la función: Girar la tortuga a la derecha
0033
Llamar a la función: fillThisRowWithEggs
0034
Llamar a la función: repeatThisUntilBoardFull
Estos ejemplos llenan la primera línea antes de la repetición principal y vuelven a visitar su casilla final al iniciar esa repetición. En TLAC, poner un huevo marca una casilla como ocupada; no apila otro huevo allí. El nombre de la función dice “Row” (fila), pero aquí la tortuga recorre una columna vertical.
Problema 7 · Llenar al subir y desplazarse al bajar
La función exterior sigue llamándose a sí misma, pero la comprobación de dirección decide qué trabajo hacer primero. La rama hacia arriba llama a fillThisRowWithEggs; la otra hace el movimiento largo. La función de llenado vuelve al llegar a la pared, mientras que el patrón completo termina al comprobar el borde derecho.
Con recursión · Problema 7
0001
Problema 7
0002
Definir la función: goToBeginningOfBoard
0003
Si la tortuga puede avanzar 1 casilla, entonces
0004
Llamar a la función: Avanzar la tortuga 1 casilla
0005
Llamar a la función: goToBeginningOfBoard
0006
En caso contrario
0007
Volver a la instrucción que sigue a la llamada
0008
Definir la función: fillThisRowWithEggs
0009
Si la tortuga puede avanzar 1 casilla, entonces
0010
Llamar a la función: Poner un huevo debajo de la tortuga
0011
Llamar a la función: Avanzar la tortuga 1 casilla
0012
Llamar a la función: fillThisRowWithEggs
0013
Volver a la instrucción que sigue a la llamada
0014
En caso contrario
0015
Llamar a la función: Poner un huevo debajo de la tortuga
0016
Volver a la instrucción que sigue a la llamada
0017
Definir la función: repeatThisUntilBoardFull
0018
Si la tortuga mira hacia arriba, entonces
0019
Llamar a la función: fillThisRowWithEggs
0020
Llamar a la función: Girar la tortuga a la derecha
0021
Llamar a la función: Avanzar la tortuga 1 casilla
0022
Llamar a la función: Girar la tortuga a la derecha
0023
En caso contrario
0024
Llamar a la función: Avanzar la tortuga — distancia: altura del tablero − 1
0025
Llamar a la función: Girar la tortuga a la izquierda
0026
Si la tortuga mira hacia la derecha, entonces
0027
Si la tortuga no puede avanzar 1 casilla, entonces
0028
Llamar a la función: Terminar programa
0029
Llamar a la función: Avanzar la tortuga 1 casilla
0030
Llamar a la función: Girar la tortuga a la izquierda
0031
Llamar a la función: repeatThisUntilBoardFull
0032
Llamar a la función: Girar la tortuga a la izquierda
0033
Llamar a la función: goToBeginningOfBoard
0034
Llamar a la función: Girar la tortuga a la derecha
0035
Llamar a la función: fillThisRowWithEggs
0036
Llamar a la función: repeatThisUntilBoardFull
La recursión puede repetir una decisión, además de un movimiento. Observa qué rama pone huevos y cuál solo se desplaza.
fillThisColumnWithEggs se llama después de cada avance de 2 casillas. Su caso de parada pone el último huevo y vuelve cuando ya no se puede avanzar otras 2 casillas. repeatThisUntilBoardFull gestiona los giros y se llama para la siguiente columna. Si no se puede avanzar 2 columnas, el programa termina en lugar de hacer otra llamada recursiva.
Con recursión · Problema 8
0001
1. Llevar la tortuga hasta la pared de enfrente
0002
Definir la función: goToBeginningOfBoard
0003
Si la tortuga puede avanzar 1 casilla, entonces
0004
Llamar a la función: Avanzar la tortuga 1 casilla
0005
Llamar a la función: goToBeginningOfBoard
0006
En caso contrario
0007
Volver a la instrucción que sigue a la llamada
0008
0009
2. Poner un huevo, avanzar 2 casillas y volver a llamar a esta función
0010
Definir la función: fillThisColumnWithEggs
0011
Si la tortuga puede avanzar 2 casillas, entonces
0012
Llamar a la función: Poner un huevo debajo de la tortuga
0013
Llamar a la función: Avanzar la tortuga — distancia: 2
0014
Llamar a la función: fillThisColumnWithEggs
0015
En caso contrario
0016
Llamar a la función: Poner un huevo debajo de la tortuga
0017
Volver a la instrucción que sigue a la llamada
0018
0019
3. Girar, avanzar 2 columnas y repetir
0020
Definir la función: repeatThisUntilBoardFull
0021
Llamar a la función: fillThisColumnWithEggs
0022
0023
Cuando la tortuga llega arriba mirando hacia arriba
0024
Si la tortuga mira hacia arriba, entonces
0025
Llamar a la función: Girar la tortuga a la derecha
0026
Comprobar si el borde derecho está demasiado cerca para avanzar 2 casillas
0027
Si la tortuga no puede avanzar 2 casillas, entonces
0028
Si la tortuga puede avanzar 1 casilla, entonces
0029
Llamar a la función: Avanzar la tortuga 1 casilla
0030
Llamar a la función: Girar la tortuga a la derecha
0031
Llamar a la función: Terminar programa
0032
Volver a la instrucción que sigue a la llamada
0033
0034
Llamar a la función: Avanzar la tortuga — distancia: 2
0035
Llamar a la función: Girar la tortuga a la derecha
0036
0037
Cuando la tortuga llega abajo mirando hacia abajo
0038
En caso contrario
0039
Llamar a la función: Girar la tortuga a la izquierda
0040
Comprobar si el borde derecho está demasiado cerca para avanzar 2 casillas
0041
Si la tortuga no puede avanzar 2 casillas, entonces
0042
Ajustar la posición final en la esquina si queda una casilla
0043
Si la tortuga puede avanzar 1 casilla, entonces
0044
Llamar a la función: Avanzar la tortuga 1 casilla
0045
Llamar a la función: Girar la tortuga a la derecha
0046
Llamar a la función: Terminar programa
0047
Volver a la instrucción que sigue a la llamada
0048
0049
Llamar a la función: Avanzar la tortuga — distancia: 2
0050
Llamar a la función: Girar la tortuga a la izquierda
0051
0052
Volver a llamar a esta función para la nueva columna
0053
Llamar a la función: repeatThisUntilBoardFull
0054
0055
0056
Instrucciones principales: empezar aquí
0057
0058
Paso A: Ir a la pared izquierda (columna 0)
0059
Llamar a la función: Girar la tortuga a la izquierda
0060
Llamar a la función: goToBeginningOfBoard
0061
0062
Paso B: Mirar hacia arriba e ir a la pared superior (fila 0)
0063
Llamar a la función: Girar la tortuga a la derecha
0064
Llamar a la función: goToBeginningOfBoard
0065
0066
Paso C: Dar media vuelta, mirar hacia abajo y avanzar 1 casilla hasta la fila 1
0067
Llamar a la función: Girar la tortuga a la derecha
0068
Llamar a la función: Girar la tortuga a la derecha
0069
Llamar a la función: Avanzar la tortuga 1 casilla
0070
0071
Paso D: Iniciar el recorrido de ida y vuelta con llamadas recursivas
0072
Llamar a la función: repeatThisUntilBoardFull
Hay dos preguntas de parada distintas: «¿Puedo seguir en esta columna?» y «¿Puedo llegar a otra columna?». Cada tarea repetida necesita su propia respuesta.
¿Cuál conviene elegir? Para un movimiento repetido sencillo, un bucle suele ser más fácil de seguir. La recursión es útil cuando el trabajo restante se parece de forma natural al trabajo original. Cada llamada pendiente necesita recordar dónde volver; una recursión muy profunda puede consumir demasiada memoria. Estos ejemplos enseñan la idea: la recursión no hace automáticamente más rápido un programa.
3. Clases y objetos
Una clase describe un tipo de cosa: la información que guarda y las acciones que puede realizar. Aquí la clase describe una tortuga. Un objeto es una tortuga concreta creada a partir de esa descripción; también se llama instancia. Aki y Sol pueden ser dos objetos de la misma clase Tortuga.
Clase: Tortuga
Atributos (información guardada): nombre, posición horizontal X, posición vertical Y y dirección.
Constructor (preparación inicial): recibir un nombre y las coordenadas X e Y; crear esta tortuga allí, mirando hacia arriba.
Método «Avanzar»: mover esta tortuga una casilla en su propia dirección.
Método «Girar a la derecha»: girar esta tortuga 90° en sentido horario; su posición no cambia.
Método «Poner un huevo»: poner un huevo en la casilla actual de esta tortuga.
Método «Marcar y avanzar»: pedir a esta tortuga que ponga un huevo y luego que avance. Un método puede usar otros métodos.
Un atributo es un dato con nombre que pertenece a un objeto. Un método es una función que proporciona su clase. «Esta tortuga» es el objeto que recibe la petición: pedir a Aki que avance cambia la posición de Aki. La definición de la clase por sí sola no crea ni mueve una tortuga. Crear un objeto ejecuta su constructor, no todos sus métodos.
Estos ejemplos usan un tablero TLAC de 6 × 6. X aumenta hacia la derecha; Y aumenta hacia abajo. La esquina superior izquierda es X=0, Y=0. Los recorridos se mantienen dentro del tablero. Las ejecuciones completas muestran cada petición a un método y las acciones de la tortuga que provoca.
Ejemplo 1: una tortuga deja un rastro de huevos
Crea Aki en X=1, Y=4, mirando hacia arriba. Pídele que marque y avance dos veces, gire a la derecha y marque y avance una vez más. Los dos movimientos hacia arriba cambian Y de 4 a 2. El último movimiento cambia X de 1 a 2. Aki termina en X=2, Y=2, mirando a la derecha, con tres huevos detrás.
Programa: el rastro de Aki
0001
Crear la tortuga Aki en X=1, Y=4, mirando hacia arriba
Empieza con un tablero nuevo. Crea Aki en X=1, Y=4 y Sol en X=4, Y=4. Ambas miran hacia arriba. Pide a Aki que marque y avance dos veces. ¡Sol no se ha movido! Ahora pide a Sol que gire a la derecha, marque y avance una vez. Aki se queda en X=1, Y=2, mirando hacia arriba; Sol termina en X=5, Y=4, mirando a la derecha.
Programa: Aki y Sol
0001
Crear la tortuga Aki en X=1, Y=4, mirando hacia arriba
0002
Crear la tortuga Sol en X=4, Y=4, mirando hacia arriba
Misma clase, estado separado. Aki y Sol usan los mismos métodos, pero cada una guarda su propio nombre, X, Y y dirección. Comparten el tablero y pueden ver los huevos que hay en él. Un huevo pertenece a una casilla, no a los atributos personales de una tortuga. La página de ejecución muestra los estados de ambas para ver cuál cambia.
«Marcar y avanzar» usa otros métodos, pero no es recursión: ese método nunca se llama a sí mismo. Las clases organizan información y acciones. La recursión permite que una función repita trabajo. Un método puede ser recursivo, pero no tiene por qué serlo.
4. Practícalo
1. ¿Qué pasa si se quita el movimiento hacia la pared?
Mostrar una respuesta
Si la tortuga empieza lejos de la pared, la siguiente llamada ve la misma posición. Sigue llamando sin alcanzar el caso base. No basta con una condición de parada: la acción repetida debe avanzar hacia ella.
2. ¿Volver desde la función que llena una columna termina todo el programa?
Mostrar una respuesta
No. Volver reanuda la función que hizo la llamada. Esta puede girar la tortuga y empezar otra columna. Terminar programa es la instrucción que lo detiene todo.
3. Aki y Sol miran hacia arriba. Pide solo a Sol que gire a la derecha. ¿Gira también Aki?
Mostrar una respuesta
No. Sol mira a la derecha; Aki sigue mirando hacia arriba. Cada objeto tortuga guarda su propio atributo de dirección.
4. Diseña un método «Dar media vuelta» para la clase Tortuga.
Mostrar una respuesta
Pide a esta tortuga que gire a la derecha dos veces. Su dirección cambia 180°, mientras X e Y no cambian. Otra tortuga del tablero debe conservar su dirección.
Recuerda: la recursión necesita un caso de parada y avanzar hacia él. Una clase describe atributos y métodos; cada objeto tiene su propio estado. Puedes seguir ambas ideas con papel, monedas y unas tarjetas de instrucciones.
