32. More recursion

The last program we considered was the following:

function go_home(){
    if (!at_goal()) {
        move();
        go_home();
    }
    turn_left();
}

// now do it!
go_home();

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 (!at_goal()) {
    move();
    go_home();
}
turn_left();

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

    move();
    go_home();
turn_left();

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

    move();
    if (!at_goal()) {
        move();
        go_home();
    }
    turn_left();
turn_left();

and do it one more time:

    move();
        move();
        if (!at_goal()) {
            move();
            go_home();
        }
        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 (!at_goal()) {
        //    move();
        //    go_home();
        //}
        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.

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

function go_home(){
    move();
    if (!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?