Recursion – weeks 11 and 12

“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:

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()

trace it


go_to_wall() - 0
wall_in_front() == False; do else


go_to_wall() - 1
wall_in_front() == False; do else


go_to_wall() - 2
wall_in_front() == False; do else


go_to_wall() - 3
wall_in_front() == True; do if



Our template…


.. becomes this:


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()

show it to me


Ready to go!

Ready to go!


Touchdown!

Touchdown!




recursion trace


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():


Our original version


Exchange the if and the else (remember to negate the condition)


Use a complementary function in base condition, if there is one available



Factor out the return statement


An empty return at the end of a function is optional; remove it


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

Work it out

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.

football-560503_640

Answer: Show it to me


Let’s start by writing the main program:


Before: Ready!

Before: Ready!


After: Touchdown!

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..


..turns to this..


..and after clean up:


go_to_wall() appears so often in our missions that we placed it in the library.

TM2 Strawberries – Dessert

Work it out

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.

torte-2243_640

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:

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:



Ready!

Ready!


Yummy.. a strawberry

Yummy.. a strawberry


3rd grade – Life in SoCal – The wall

Work it out

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's rendition)

The “Curiosity” rover in Mars (artist rendition)



“Hum.. piece of cake,” we say. “The main program should be something like this:”



Answer: Show it to me


Just landed!

Just landed!


I made it!

I made it!


4th grade – Strawberries – Whistle while you work

Work it out

strawberry-260688_640Karel 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:

and use them to solve the problem.

Answer: Show it to me


About to move the plants against the fence

About to move the plants against the fence


Done!

Done!


5th grade – The rooms of Doom – The treasure of the incas

Work it out

machu-picchu-43387_640We 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

Answer: Show it to me

Here we go!

Here we go!

We did it!

We did it!

6th grade – Life in SoCal – Corn maze

Work it out

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

Corn maze at the Bishop’s Pumpkin Patch in Wheatland, CA

Answer: Show it to me

Pumpkin... pumpkin..

Pumpkin… pumpkin..

nice!   =-)

nice! =-)

Hint:

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.