One difficulty in learning about recursion is the "you're allowed to do that?" aspect, where defining something in terms of itself can feel "incomplete" or "cir

One difficulty in learning about recursion is the "you're allowed to do that?" aspect, where defining something in terms of itself can feel "incomplete" or "circular". This problem is possibly confounded by the fact that some recursive definitions in computer science are "incomplete" or "circular" (they can be proved not to terminate, or cannot be proved to terminate, and so can't actually be evaluated!). We're used to the idea that a circular argument (the original sense of "beginning the question") is unpersuasive and that a circular definition or answer is unhelpful. So it's subtle to see when a partly self-referential definition can actually be usable. In functional programming languages you might only be able to use recursion when you can prove it always reaches the base case (to define a total function), but that requirement is itself somewhat subtle!