# To officially be recursion, must there be a base case?

In this Python code, the function f is defined, which then immediately calls itself:

def f():
f()


It's not very complicated, the first line defines the function, and the second line calls it. Therefore, once the function is initially called, it will be continued to be called forever, as there is no base case.

I just wanted to know if, from a mathematical standpoint, this was a real example of recursion (or at least met the mathematical definition of recursion)? While it may be rather pointless, I'm just curious as to whether or not it would actually be considered recursion.

-
What you wrote is indeed a recursive definition of a function. –  Mariano Suárez-Alvarez Feb 23 '12 at 9:57
There is no need for a base case in a recursive definition. A beautiful, tantalizing example is the definition of a game given by Conway in his extraordinary On Games and Numbers. –  Mariano Suárez-Alvarez Feb 23 '12 at 9:58
There's always a base case in a recursive definition, but sometimes the base case is so trivial no-one ever thinks about it. The base case for Conway's games is the empty game $\{ \quad \mid \quad \}$. –  Zhen Lin Feb 23 '12 at 10:37

In recursion theory, a branch of formal number theory and computability theory, the function that never returns does count as a "recursive" function (which here simply means that it is computable). On the other hand, recursion theory also has a technical meaning of "recursive definition", which your particular definition of a function-that-never-returns does not satisfy. There are some restrictive requirements about always having a particular base case and always subtracting one in the recursive call that it doesn't meet.

However, most other bona-fide recursive subroutines in computer programs would also fail the restrictive sense of "recursive definition" from recursion theory. It's not meant to describe actual programming practice, or even the kind of recursive definitions commonly used in other areas of mathematics.

Alternatively, in denotational semantics of programming languages (which organizatorially is counted as computer science, but whose current research frontier looks a lot like mathematics), there is a much more expansive concept of recursive definition, which your infinite recursion fits well into.

It is easier to explain by using a less trivial example, however. So let's take the following example (computing modulus 42 for positive arguments): $$\forall n \qquad f(n) = \begin{cases}n&0\le n<42\\ f(n-42)&\text{otherwise}\end{cases}$$ To interpret this, we first separate the $f$ being defined from the $f$ inside the body: $$\forall n \qquad g(n) = \begin{cases}n&0\le n<42\\ f(n-42)&\text{otherwise}\end{cases}$$ and then write $g$ itself as a function of $f$: $$\forall n, f \qquad \Phi(f)(n) = \begin{cases}n&0\le n<42\\ f(n-42)&\text{otherwise}\end{cases}$$ This equation now defines a non-recursive operation $\Phi$ that takes functions as input and produces new functions as output. We want to define an $f$ such that $\Phi(f)=f$, that is, $\Phi(f)$ and $f$ are the same (mathematical) function. In yet other words, we want that $f$ is a fixed point of $\Phi$.

However, the equation $\Phi(f)=f$ may not define $f$ fully. Certainly it is satisfied by the "intended" solution (which gives modulus 42 for positive arguments and 0, but diverges for negative arguments). But the function that gives modulus 42 for positive arguments and always returns $7$ for negative arguments also satisfies the equation.

It turns out that under certain computationally reasonable restrictions on $\Phi$, there is a unique fixed point, called the least fixed point, such that if $f$ is the least fixed point and $g$ is any fixed point, then $f\subseteq g$, where a function $f$ is identified with the set $\{(x,y)\mid f(x)=y\}$ -- in order words for any $n$ such that $f(n)$ terminates $g(n)$ terminates with the same result. Furthermore, the least fixed point is exactly what one would expect to get out of executing the recursive definition as a program.

The "certain restriction" is that $\Phi$ must be monotonic, i.e., that if $f\subseteq g$ for any $f$ and $g$, then $\Phi(f)\subseteq \Phi(g)$. Letting $g$ terminate more often than $f$ cannot make $\Phi(g)$ terminate less often than $\Phi(f)$, or produce different results on the inputs where $\Phi(f)$ does terminate. (This is automatically the case if the only way $\Phi(f)$ can depend of $f$ is asking for certain values of $f(n)$ and then having to loop infinitely if $f(n)$ does so -- exactly how one would expect an actual program to work). When this is the case, the least fixed point can be defined mathematically as the infinite union $$\Phi(\emptyset)\cup \Phi(\Phi(\emptyset))\cup\Phi(\Phi(\Phi(\emptyset)))\cup\cdots$$

How does your Python function fit into this framework? It does so beautifully: $$\forall f:\{\bullet\}\to S, \forall s\in\{\bullet\} \qquad \Phi(f)(s) = f(s)$$ where $\bullet$ is some dummy value that indicates the absence of arguments. With $\emptyset$ being the everywhere undefined function, we see that $\Phi(\emptyset)=\emptyset$, and therefore $\emptyset$ is the least fixed point.

So in this framework, your definition is a perfectly good recursive definition, but the function it defines happens to be the everywhere undefined one.

[A number of interesting points about lazy evaluation and/or closures have been swept under the rug to simplify the exposition].

-