CS217 Precept 4: Recursion

Starting with recursion

Recursion is a technique that you'll see over and over again. While it always confuses folks in the beginning, and the examples we use are pretty lame, it's a powerful technique you'll be using all the time in your computer career. Bear with it; it's pretty cool.

Recursion is all about reducing a problem to simpler or smaller sub-problems. Eventually, you've simplified the problem to the point that you've got a simple example. If you've ever done a proof by induction in mathematics, then you've seen this before.

Let's have a look at everybody's first recursive program - factorial.

N! = N * (N-1) * (N-2) * . . . * 1
We know that N! = N * (N-1)! and we know that 0! = 1. Putting them together, we can write a concise program without any for-loops or other fancy syntax.

Everybody's second recursive program is fibonacci, which is just like factorial, only it's recursive definition is a little more complicated.

Fib(N) = Fib(N-1) + Fib(N-2)
Fib(0) = Fib(1) = 1
We get a sequence that looks like this:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
Again, we've got code that calls itself, which seems like it should be illegal in certain countries. Sure, you could write a for loop and it will run faster. However, the recursive C code exactly matches the definition of the Fibonacci numbers. Next week, we'll give you some examples that you can't easily turn into for loops, so get into it.
Aside: The argument about for-loops has always been used against recursion, but it's not necessary. Have a look at this alternate factorial version. It uses tail-recursion, which means that the value we return is just another call to the recursive function. When you do this, the compiler can actually turn your program into a loop behind your back!

Drawing lines recursively

I'm worried I'm starting to sound like Bill Nye, The Science Guy, but you can do some really neat stuff with recursion.

Let's try drawing a line. When you're using a computer, it draws lines on the screen. How do you suppose they do it? If you feel the need for speed, then you're going to use Bresenham's line drawing algorithm. From that hyperlink, you can probably tell that Bresenham's algorithm is pretty complicated. Here's a very simple alternative.

We can define a line recursively as follows:

I've written some C code which spells this out in more detail.

In class, we'll walk through this and come to the startling conclusion that it's broken and we've got to fix it. To diagnose the bug, we'll draw a figure like this:

and walk through drawing a line from 2 to 6. For starters, you'll notice that 2 and 6 never got plotted, only 3, 4, and 5. You'll also notice that the termination condition isn't strong enough - there are cases where the recursion never stops. Can you fix it? Will your fix work properly when the line is two-dimensional instead of just along one line?

Here's the correct version of the C code.

Dan Wallach, CS Department, Princeton University
Last modified: Thu Feb 29 15:01:13 EST 1996