4.6 Introduction: Visualizing Recursion

In the previous section we looked at some problems that were easy to solve using recursion; however, it can still be difficult to find a mental model or a way of visualizing what is happening in a recursive function. This can make recursion difficult for people to grasp. In this section we will look at a couple of examples of using recursion to draw some interesting pictures. As you watch these pictures take shape you will get some new insight into the recursive process that may be helpful in cementing your understanding of recursion.

For our illustrations we will use a simple code I made available at https://github.com/pmary/js-turtle-graphic. This, allow us to use simple commands similar to the Python’s turtle graphics module. The metaphor is quite simple. You can create a turtle and the turtle can move forward, backward, turn left, turn right, etc. The turtle can have its tail up or down. When the turtle’s tail is down and the turtle moves it draws a line as it moves.

We will use the turtle class in turtle.js to draw a spiral recursively.

var canvas = document.getElementById('c');
var arrowCanvas = document.getElementById('a');
canvas.width = window.innerWidth;
canvas.height = window.innerHeight;
arrowCanvas.width = window.innerWidth;
arrowCanvas.height = window.innerHeight;

var turtle = new Turtle(canvas, arrowCanvas);

function drawSpiral(turtle, lineLen) {
  if (lineLen > 0) {
    turtle.forward(lineLen);
    turtle.left(90);
    drawSpiral(turtle, lineLen-5);
  }
}
drawSpiral(turtle, 100);
turtle.draw();

We first set the size of two canvas, one is to draw the lines and the other one is to draw the arrow that will represent our turtle. Then, we create a turtle and define the drawSpiral function. The base case for this simple function is when the length of the line we want to draw is reduced to zero or less. If the length of the line is longer than zero we instruct the turtle to go forward by lineLen units and then turn right 90 degrees. The recursive step is when we call drawSpiral again with a reduced length. At the end you will notice that we call the function turtle.draw(). This method start the animated drawing process of the previous instructions.

forward, backward, left and right methods is all that you need to know in order to make some pretty impressive drawings. For our next program we are going to draw a fractal tree. Fractals come from a branch of mathematics, and have much in common with recursion. The definition of a fractal is that when you look at it the fractal has the same basic shape no matter how much you magnify it. Some examples from nature are the coastlines of continents, snowflakes, mountains, and even trees or shrubs. The fractal nature of many of these natural phenomenon makes it possible for programmers to generate very realistic looking scenery for computer generated movies. In our next example we will generate a fractal tree.

To understand how this is going to work it is helpful to think of how we might describe a tree using a fractal vocabulary. Remember that we said above that a fractal is something that looks the same at all different levels of magnification. If we translate this to trees and shrubs we might say that even a small twig has the same shape and characteristics as a whole tree. Using this idea we could say that a tree is a trunk, with a smaller tree going off to the right and another smaller tree going off to the left. If you think of this definition recursively it means that we will apply the recursive definition of a tree to both of the smaller left and right trees.

Let’s translate this idea to some JavaScript code:

function tree(branchLen, turtle) {
    if (branchLen > 5) {
        turtle.forward(branchLen);
        turtle.right(20);
        tree(branchLen - 15, turtle);
        turtle.left(40);
        tree(branchLen - 15, turtle);
        turtle.right(20);
        turtle.backward(branchLen);
    }
}

Let’s look at the code a bit more closely. You will see that on lines 5 and 7 we are making a recursive call. On line 5 we make the recursive call right after the turtle turns to the right by 20 degrees; this is the right tree mentioned above. Then in line 7 the turtle makes another recursive call, but this time after turning left by 40 degrees. The reason the turtle must turn left by 40 degrees is that it needs to undo the original 20 degree turn to the right and then do an additional 20 degree turn to the left in order to draw the left tree. Also notice that each time we make a recursive call to tree we subtract some amount from the branchLen parameter; this is to make sure that the recursive trees get smaller and smaller. You should also recognize the initial if statement on line 2 as a check for the base case of branchLen getting too small.

By running the code, notice how each branch point on the tree corresponds to a recursive call, and notice how the tree is drawn to the right all the way down to its shortest twig. Now, notice how the program works its way back up the trunk until the entire right side of the tree is drawn. Then the left side of the tree is drawn, but not by going as far out to the left as possible. Rather, once again the entire right side of the left tree is drawn until we finally make our way out to the smallest twig on the left.