3. More recursion

The last program we considered was the following:

def go_home():
    if not at_goal():
        move()
        go_home()
    turn_left()

# now do it!
go_home()      # first call

By now, you probably have figured out how it works; at the very least, you should have tried to run it! Let’s analyze it assuming we run it in world Home 1. As usual, we consider the single instruction:

go_home()

which gets replace by the body of the function definition:

if not at_goal():
    move()
    go_home()    # second call
turn_left()

Since Reeborg has not reached its goal yet, the if statement block is executed:

move()
go_home()        # second call
turn_left()

Once again, we replace go_home() by its definition:

move()
if not at_goal():
    move()
    go_home()    # third call
turn_left()
turn_left()

and do it one more time:

move()
move()
if not at_goal():
    move()
    go_home()    # would be fourth call
turn_left()
turn_left()
turn_left()

After the second move() instruction, Reeborg has reached its goal and the if statement block is not executed:

move()
move()
if not at_goal():
    move()      # not called
    go_home()   # not called
turn_left()
turn_left()
turn_left()

Note

go_home is called three times ... and Reeborg does three left turns. This is perhaps something that Reeborg can use to count ... Remember this!

Thus, after reaching its goal, Reeborg does three left turns (a celebratory dance perhaps?) before ending its program.

Try it!

By running it, check that the recursive program does indeed result in having Reeborg make three left turns at the end.

3.1. Another test

Using again the same world, can you figure out what would be Reeborg’s final orientation if he executes the following program?

def go_home():
    move()
    if not at_goal():
        go_home()
        turn_left()
    turn_left()

# now do it!
go_home()

Do this!

Try to figure out the above program without running it and then check your understanding by seeing Reeborg in action. What would happen if Reeborg were already at its goal before running the program?