Up: Recursion.

How can you tell if a recursive definition is well-defined? Here's one easy way that often applies: If each time you recurse you are significantly closer to the base case, then the definition isn't circular. For example, our definition of Jewishness is well-defined since each time we go back a generation, we are at least one year closer to Sarah.

*Significantly* closer? I include the word
*significantly*, since the following program always gets closer
to the base case of 0, but it never quite gets there.

This isn't circular, but it's still not well-defined. In most well-defined cases that turn up in reality, we can say we get at least 1 step closer to a base case (as happens withFUNCTION WellDefinedExample(x) IF x == 0, THEN: return 0 ELSE: return WellDefinedExample(x / 2) END IF

Sometimes it is very hard to tell whether a definition is circular. The Syracuse problem dates from the 1930s, and mathematicians still don't know whether it's circular or not. It's a pretty simple recurrence.

If

If