“Never, never, never give up”
-Churchill
Handout: 6_intro_1_recursion
Recursion
Recursion is a technique in which a function calls itself over and over solving progressively smaller versions of the same problem. All recursive functions follow a template similar to this:
def: if : # is the problem solved or almost solved? # solve it return else: # otherwise if the problem is not solved... # ...reduce problem a bit and.... # ...try to solve it again return
In Python, the returns at the end of the bodies of the if and the else are not necessary but we will leave them there for now to make clear what is happening.
Unlike the functions that we have seen so far, a recursive function always may return from two different locations. The following are the parts of a recursive function:
- base condition: This is a condition (or conditions) that tells us that the problem is either already solved or that its solution is very easy. Hence, if the base condition is True, we simply solve the problem and return.
- base case: These are the instructions that we run if the base condition is True; many times the base case is empty, i.e., there is nothing to do, so often we simply return
- recursive case: This is the key of recursion: we split the problem into smaller versions of the same problem, each of which is closer than the original problem to the base condition
- recursive call: we try so solve the smaller versions of the original problem by calling the function again.
Example: go_to_wall()
wall_in_front() == False; do else
wall_in_front() == False; do else
wall_in_front() == False; do else
wall_in_front() == True; do if
Our template…
def: if : # easy case # body of the if return else: # recursive case # reduce problem # ...try again return
.. becomes this:
def go_to_wall():
if wall_in_front(): # easy case
pass # body of the if
return
else: # recursive case
move() # reduce problem
go_to_wall() # ...try again
return
where pass is a Python instruction that does nothing. As long as there is a wall in front of Karel, this function works regardless of Karel’s initial position.
Example: scoring a touchdown()
Ready to go!
Touchdown!
def go_to_wall():
if wall_in_front(): # easy case
pass # body of the if
return
else: # recursive case
move() # reduce problem
go_to_wall() # ...try again
return
# main program
move()
take()
go_to_wall()
put()
Example: cleaning the solution
As we become familiar with recursion we will find that we can rearrange the template to clean up the function. For example, let’s clean go_to_wall():
def go_to_wall():
if wall_in_front():
pass
return
else:
move()
go_to_wall()
return
Our original version
def go_to_wall():
if not wall_in_front():
move()
go_to_wall()
return
else:
pass
return
Exchange the if and the else (remember to negate the condition)
def go_to_wall():
if front_is_clear():
move()
go_to_wall()
return
else:
pass
return
Use a complementary function in base condition, if there is one available
def go_to_wall():
if front_is_clear():
move()
go_to_wall()
else:
pass
return
Factor out the return statement
def go_to_wall():
if front_is_clear():
move()
go_to_wall()
else:
pass
An empty return at the end of a function is optional; remove it
def go_to_wall():
if front_is_clear():
move()
go_to_wall()
The body of the else is not doing anything; remove it
All these versions of go_to_wall() are recursive. The first version is very clear, indicating the base and the general cases. The last version is still clear once you become familiar with recursion; it says that the base case does nothing and simply returns.
The size of the function is never a good reason to modify it; clarity is our guiding principle: if we can reduce the size of the function without reducing its clarity we should do so, otherwise we should not.
TM1 Life in SoCal – Wide receiver
Karel is practicing sprints to the end zone. He has to go forward, pick up the first ball he encounters, and then dash to the end zone. The location of the ball and Karel’s distance from the end zone vary from play to play; make sure your program works for all the cases.
Answer: Show it to me
Let’s start by writing the main program:
# main program go_to_token() # ball take() go_to_wall() # endzone put() # score
Before: Ready!
After: Touchdown!
We already saw go_to_wall(); go_to_token() is similar except that the end condition is to find a token instead of a wall:
Our template..
def: if : return else: return
..turns to this..
def go_to_token():
if token_here:
pass
return
else:
move()
go_to_token()
return
..and after clean up:
def go_to_token():
if cell_is_empty():
move()
go_to_token()
go_to_wall() appears so often in our missions that we placed it in the library.
TM2 Strawberries – Dessert
To go to Karel’s house he needs to go to the end of an alley, take a right, and then walk straight until he finds it. On his way home, Karel wants to pick up a single strawberry in the alley, if he happens to find one; each cell of the alley has either 0 or 1 strawberries. Karel starts at the entry of the alley with an empty bag. Take Karel home, with a strawberry, if possible.
Answer: Show it to me
We are going to solve the problem splitting it 3 ways. First, we are going to move until we find the strawberry or the wall, then we are going to move to the end of the alley, and finally we are going home. The check_for_strawberries() and go_to_wall() commands could be combined but, by splitting them here, we can create a very general function that we could add to the library, i.e., go_to_wall(). So, here is the main program:
# main program go_to_token_or_wall() # find either a strawberry or the wall safe_take(): # if found a strawberry take it go_to_wall() # go the the end of the alley right() # take a right... go_home() # go south until Karel gets home
now let’s solve the pieces.
- go_to_wall(): we already have it
- go_home(): like go_to_wall() except that we stop at home instead of a wall
- go_to_token_or_wall(): like go_to_wall() except that we stop at either a wall or a token
The result is:
from my_lib import *
def go_to_token_or_wall():
if token_here() or wall_in_front():
return
else:
move()
go_to_token_or_wall()
def go_home():
if not at_home():
move()
go_home()
# main program
go_to_token_or_wall()
safe_take()
go_to_wall()
right()
go_home()
Ready!
Yummy.. a strawberry
3rd grade – Life in SoCal – The wall
JPL is testing Karel’s ability to return to base after unforeseen events. Some of the most interesting places in Mars are the inside of craters. They are also some of the most dangerous places because if the robot lose his bearings, it might be difficult to return to the base. In the following scenario, Karel is dropped at a random position south of a crater’s wall that is miles long. Karel needs to head north until he finds the wall and then hug the wall on the right until he finds the opening where the base is located.
The “Curiosity” rover in Mars (artist rendition)
“Hum.. piece of cake,” we say. “The main program should be something like this:”
# main program face_north() go_to_wall() find_door() move()
Answer: Show it to me
Just landed!
I made it!
4th grade – Strawberries – Whistle while you work
Karel had planted some strawberries at the public plaza, away from the fences. The strawberries are growing and have become a tourist attraction so the city council has asked Karel to move them against the fences so more people can admire them safely; Karel is happy to help the city council. A pot can have any number of plants. Karel starts with an empty bag. Please help him make the city council happy. To do this we will need to write the following functions in a recursive fashion:
take_all() # take all the tokens in the cell put_all() # put on the floor all the tokens in Karel's bag
and use them to solve the problem.
Answer: Show it to me
About to move the plants against the fence
Done!
5th grade – The rooms of Doom – The treasure of the incas
We find ourselves under Machu Picchu, in Perú, in a room that contains a star. The path to the star was cleverly codified to trap intruders in the maze but.. we got the code, so with a little patience we have a good chance to get there.
The strategy is deceptively simple: at every wall that we encounter, we have to turn left if we found a token, or turn right otherwise.
Is that it? Well.. yeah.. there are plenty of decoy tokens trying to mislead us but, if you know the code (which we do), we should be able to get the star.
To take a start use
take( "star" )
Answer: Show it to me
Here we go!
We did it!
6th grade – Life in SoCal – Corn maze
A popular attraction around Halloween is to visit farms that hide pumpkins within corn mazes. Karel is a fan of pumpkin pie and this year he has decided to get the biggest (and only) pumpkin of all. Please, help Karel to get the pumpkin and then take him home.
Missions with mazes appear to be very difficult but in reality they are quite easy as long as the maze does not have islands; all that is needed is to walk hugging a wall and eventually, you will visit every cell of the maze.
Corn maze at the Bishop’s Pumpkin Patch in Wheatland, CA
Answer: Show it to me
Pumpkin… pumpkin..
nice! =-)
Break the problem in pieces. First we need to collect the pumpkin; then we need to go home.
To collect the pumpkin, break the problem again. First see if Karel is standing on the pumpkin; if he is not, he needs to move hugging the wall.
To hug the right wall, turn to the right and make sure the wall is there. Whether it is there or not, find the next direction of motion and step in that direction.