Tuesday, March 21, 2006

Clarifying Recursion

I managed to confuse a lot of people yesterday in my post on building math, because I forgot that normal people don't understand recursion. For a computer scientist, or a mathematician involved in logic, recursion is so fundamental that it's easy to forget that when you first see it, it looks like some kind of bizzare magic. In my day job, where I'm currently doing software development, I use recursion every day.

Hopefully I can clear up that confusion.

The cleverest definition that I've seen of recursion comes from the Hackers dictionary. In there, it has:

Recursion

see "Recursion"

Recursion is about defining things in terms of themselves. For example, think about the factorial. For any positive integer N, the factorial of N (written N!) is the product of all of the integers less than it:

• 1! = 1
• 2! = 1 * 2 = 2
• 3! = 1 * 2 * 3 = 6
• 4! = 1 * 2 * 3 * 4 = 24
• 5! = 1 * 2 * 3 * 4 * 5 = 120
• ...

But that's a cumbersome way of saying it. Instead, if you look at it, you can seee that there's a pattern: the factorial of each number N is the product of a sequence of numbers, and that sequence is exactly the same as the sequence for the number before it, with N added onto the end.

Let's use that fact to make the list a bit simpler; let's just replace the sequence for everything but N with the product of the numbers in that part of the sequence:

• 1! = 1
• 2! = 1 * 2 = 2
• 3! = 2 * 3 = 6
• 4! = 6 * 4 = 24
• 5! = 24 * 5 = 120
• ...

Now the pattern should be reasonably easy to see: look at 4! and 5!; 4! = 24; 5! = 5 * 24. Since 4! is 24, we can then say that 5! = 5 * 4!.

So we can say that in general, N! = N * (N-1)!.

Except that that doesn't quite work. Let's take a look at why. Let's use that to compute 3!: 3! = 3 * 2! = 3 * 2 * 1! = 3 * 2 * 1 * 0! = 3 * 2 * 1 * 0 * -1! = ...

To make recursion work, you need to define a base case: that is, you need to define a starting point. For factorial, the way we do that is say that the factorial of 0 = 1. Then things work: factorial is only supposed to work for positive numbers; and for any positive number, the recursive definition will expand until it hits 0!, and then it will stop. So let's look at 3! again:

3! = 3 * 2! = 3 * 2 * 1! = 3 * 2 * 1 * 0! = 3 * 2 * 1 * 1 = 6.

The way that we write a recursive definition is to state the two cases using conditions, in something that looks almost like a little bit of a program:

• N! = 1 if N = 0
• N! = N * (N-1)! if N > 0

Recursion is often used in math in another way: often, one of the easiest ways to prove something is called induction; induction is nothing but using recursion to define a proof.

For a very typical example, we can look at something similar to recursion. What if we want to take the sum of every number from 1 to N? Let's write that as S_N. Well, there's an equation for it: the sum of all of the integers from 1 to N = S_N = N*(N+1)/2. Here's how we can prove that.

• We start with a base case. Let's do two of them, just for the heck of it:

• if N = 1, then the sum of all integers from 1 to 1 = 1. According to the equation, that's 1(1+1)/2 = 2/2 = 1.
• if N = 2, then it's the sum of all integers from 1 to 2 = 1 + 2 = 3. According to the equation, that's 2(2+1)/2 = 2*3/2 = 3.

• Now we look at the inductive case. We assume that the equation is true for a value N, and we prove that if it's true for N, then it will also be true for N+1.

• Assume that S_N = N*(N+1)/2
• We want to prove that S_(N+1) = (N+1)(N+2)/2.
• We know that S_(N+1) = (N+1) + S_N
• We can expand that to: (N+1) + N(N+1)/2
• We can expand further: (N+1) + (N^2 + N)/2
• We can multiply (N+1) by (2/2) so that we can combine things; since 2/2=1, that doesn't change anything: (2N+2)/2 + (N^2 + N)/2
• Now we can add the numerators: (N^2 + 3N + 2)/2
• Now we factor the top: (N+1)(N+2)/2.

• So, we've shown that for 1 and 2, the equation holds. Since it holds for two, by the induction it holds for 3. If it holds for 3, by the induction, it holds for 4, and so on.

If you followed this, congratulations, you understand recursion! If you didn't, please ask questions in the comments, so that I can try to fix this until it's comprehensible.

• I remember from CS101 the simple task we had of writing in lisp a program to calculate X^Y, x>0,y>0.

Most people used the algorith:
X^Y=
1, if y=0; otherwise,
X*(X^(y-1))

Some came up with the faster:
X^Y=
1, if y=0; otherwise,
(X^(y/2))^2 if y is even
X*(X^(y-1) ) if y is odd

By  Anonymous, at 10:42 AM

• Have you thought of becoming a teacher? Maybe later on in life once you're done being a code monkey :)
I love this blog, this is one of the best new blogs I've seen in a while. Please keep it up.

By  franky, at 12:05 PM

• franky:

Yes, I have frequently thought about being a teacher. The one thing that I don't like about my current job is that I don't get to teach.

Problem is, there are two ways you can teach math/cs: became a college professor; or become a high school teacher. I haven't published enough to be able to realistically compete for a college job (it's *very* competitive in CS, which is really my field), and high school - well, aside from all of the other problems, as someone without a degree in education, most high school math teachers start for around 1/4th of my current salary. And I've got two kids and a mortgage! :-)

So for now, my teaching is on the blog, and I'm enjoying it, because I haven't been able to do anything remotely like teaching for close to 10 years, and I really miss it.

By  MarkCC, at 12:41 PM

• In your previous post you briefly mentionned the hole that Godel blew in mathematics and avoiding self-reference dodges that bullet. Doesn't non-trivial recursion put you back in danger?

By  BMurray, at 1:13 PM

• markcc,
I feel you about the mortgage and the two kids. I'm expecting my third in October.
My current plan is to work in my current high-paying job for a number of years and then become a high-school calculus teacher. Don't really want to be a college prof.
Just a friendly suggestion

By  franky, at 1:15 PM

• That's third child, not mortgage :P

By  franky, at 1:16 PM

• bmurray:

The Godel self-reference problem comes into play when a formal system self-references itself: recursive programs and recursive definitions are, in general, OK, so long as they live within the system, and don't do any self-reference.

(To be a tad more precise; what Godel really says is that if you have a complete consistent formal system, then there are models for that system that will violate either completeness or consistency. That's a tricky idea, but the gist of it is that you *can* create self-referential systems in a variety of subtle ways, even in systems carefully constructed to avoid self-reference.

The saving grace of common recursive definitions is that they're bounded. What that means is that there's a quantity in the definition which takes discrete steps closer to the base in every iteration.

In factorial, you're reducing by one with every invocation, and stopping at zero. If you can put a finite bound on the recursion, you've avoided Godel self-reference, but you're limited in what you can do.)

By  MarkCC, at 1:38 PM

• Even in CS, people often don't really know recursion. At my first job, i wrote a recursive decimal output subroutine. It worked, but my boss complained that he didn't understand it. He spent a couple days rewriting it with a loop. That's right, he fixed my working code. My main thought was that since i'm self taught in this business, and those with real educations were this deficient, then clearly there should be a market for a person who has a clue. But it's difficult sales. You can't go in and say, well, i know recursion - because they have no idea what you are talking about. You have to somehow demonstrate that you know what you're doing.

My sales skills are so bad that i can't even give away free software that is clearly superior in every respect to what the prospective client is trying to use.

By  Stephen, at 3:46 PM

• When I started reading this post, I was thinking that you ought talk about how the recursion idea gets used in inductive proofs. And sure enough you did. You are doing a fine job.

Perhaps this is also already on your list, but group theory could provide some good posts as well. Besides being able to present abstractions like partitions, you can also present many physical examples like rotations and reflections to ground it in something easier to understand.

By  driftwood, at 8:42 PM

• Here's a simple-minded recursion example. Perhaps you've seen it.

A postcard type greeting card (no foldout) with the phrase "How to keep an idiot busy -- please turn over." The other side of course says, "Please see other side."

I teach high school physics. I sympathize with your reasons not to become a high school teacher. There are some great rewards in teaching, but none of them are financial. When you're ready, though, private schools typically do not require education degrees, just expertise in your field. Doing some tutoring or helping in some extra-curricular way will provide you some experience with school-age children.

Teaching in public schools is a different story, though there are master of arts in teaching programs at many universities and emergency certification procedures for badly needed subject teachers. Either course would enable you to enter the public schools. The pay is usually better than at private schools, but the working conditions are generally more stressful.

By  wheatdogg, at 12:28 PM