Jason M. Grant

Assistant Professor of Computer Science

Recursion with Pending Operations

Let’s begin by reviewing factorials from our previous class.

LaTeX: 5!\:=\:5\:\cdot\:4\:\cdot\:3\:\cdot\:2\:\cdot\:1

Similarly, we can compute the value of the factorial of 4.

LaTeX: 4!\:=\:4\:\cdot\:3\:\cdot\:2\:\cdot\:1

By substitution, we can say that 5! is also equal to 5*4!.  Therefore, in the general case.  

LaTeX: n!\:=\:n\:\cdot\:\left(n-1\right)!

What happens if we must solve for the factorial of 1? This equals 1 times the factorial of zero. By definition, the factorial of zero is 1. This is what we call the base case. It tells our recursive function when to stop. Therefore, we can express the factorial of n as

Let’s look at another similar example, except this problem has two base cases.

Fibonacci Numbers

The next number Fibonacci sequence is based upon the previous two numbers in the sequence. Using this information, we can calculate the n-th number of a Fibonacci sequence, if we know the value of the (n-1)^th number of the sequence and the (n-2)^th  number of the sequence. Fibonacci numbers follow the sequence 1, 1, 2, 3, 5, 8, 13, 21, 34,… Can you see the pattern?

We can find the -th number in the sequence if we know the previous two. Therefore, we can write a recursive solution. Now we just need the base cases. We know that the first and second position in our sequence are 1 and 1. Therefore, we can define the base case and implement the recursive solution.

Many of the recursive problems that you have seen so far can also be solved using methods of iteration. Let’s look at some problems that are a little bit more difficult to solve using iteration. We will also get some practice drawing with the turtle as well.

Koch Curve

The Koch curve is a fractal – a shape that is self-similar, that is, it can be decomposed into smaller versions of the same shape.

Many of the techniques that we use to generate fractals computationally rely on the repetition of a set of steps, so we tend to talk about generations, which are the number of iterations that we used to produce the drawing. The Koch curve is a fairly simple one, and we can see its structure most clearly, by looking at how it changes from one generation to the next.

The starting place (generation 0) is a straight line.

Generation 0 Koch Curve

For the first generation, we cut the line into thirds and replace the middle segment with two segments of the same length, forming two sides of an equilateral triangle.

Generation 1 Koch Curve

The second generation is formed by applying this same process to every line in generation 1.

Generation 2 Koch Curve

Further generations are formed by repeating this process, taking each line, breaking it into thirds and replacing the middle segment with a bump. Conceptually, if you take this out to infinity, you will have a very curious mathematical phenomenon – an infinitely long line between two fixed points a finite distance away that also occupies a finite area. In practical terms, however, when the length of the line becomes 1 pixel long, that is pretty much as small as we can get.

Generation 3 Koch Curve

To actually draw the shape, our process will really be the opposite of what is described above. We don’t want to draw a line and then go back and remove a piece. Instead, we will start with the highest generation of the fractal first. If you think about a generation 2 curve, it is really made up of four generation 1 curves that are each 1/3 the length of the generation 2 curve. But each of those generation 1 curves are made up of generation 0 curves 1/3 of thatlength. What that means is that we don’t actually drawany of the higher generation curves, the only thing we draw is a whole bunch of generation 0 curves (straight lines!) in different locations.

Pending Operations

What if we wanted to undo? Can we retrace our steps. Let’s look at functions with pending operations. You have seen some examples of this before, but this problems will help to clearly illuminate the pending operation.

Here is a second example of pending operations using a drawing example. First, we begin by drawing a line. To do so, we move a distance Lforward. We execute some commands and then move back by the same distance L.

Drawing Curve and Retracing