Up: Recursion.

Avoiding circularity

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.

FUNCTION WellDefinedExample(x)
IF x == 0, THEN:
	return 0
ELSE:
	return WellDefinedExample(x / 2)
END IF

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 with isAJew).

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.

S(1) = 0
If n is odd, S(n) = 1 + S(3n + 1)
If n is even, S(n) = S(n/2)
We know it's not circular for reasonable values of n, but we don't know if there's some n out there for which the definition cycles.