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