## Jason M. Grant

Assistant Professor of Computer Science

## Recursion with Pending Operations

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

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

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

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.

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.

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

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. 