I'm reading a functional programming book that comes from a very heavy mathematical perspective and I got stuck on trying to understand and expand a statement about recursive equations. It states:

Some systems of recursive equations do not define functions; for example

$f n = f (n + 1)$.

Every constant function satisfies the equations for $f$, but none is defined by it.

Can someone explain and expand this last sentence please?

  • 1
    $\begingroup$ My reading of this would be that although every constant function satisfies $f(n)=f(n+1)$, this recursive equation does not lead to a specific constant function. As an example, $f(x)=42$ would satisfy the recursive equation $f(n)=f(n+1)$, but you could not define the function $f(x)=42$ by the recursion $f(n)=f(n+1)$ as this recursion leads to an infinite number of constant functions and not just $f(x)=42$. $\endgroup$ – Mufasa Feb 23 '16 at 20:36
  • $\begingroup$ @Mufasa, yes this makes sense now. $\endgroup$ – M.K. Feb 23 '16 at 20:39

A recursive definition of a function (or anything else for that matter), is given from one ore more "recursive equations", with the name of the recursive function ('f' in your example) as "the unknown". Now if that equation(s) has a unique solution, then we can say that the function is defined (uniquely determined) from said equation(s); we can now think of the equation(s) as some sort of "implicit definition".

It has nothing to do with recursion or functions per se; while $x = 2$ or $3x=0$ "define" numbers (2 and 0 respectively), the equations $0\cdot x=0$, $x=x$ and $0\cdot x=17$ do not (either because no solution exists as in $0\cdot x=17$ or the solutions are not unique).

Now the thing with recursive definitions is, that it can be shown, that when certain conditions are met (roughly "there is a well founded relation underlying the recurrence"), then a unique solution for the given equation exists.

In your example $f(x)=f(x+1)$, the underlying relation is the "greater than" relation, which is not well founded and indeed no unique solution for that equation exists (as stated all constant functions satisfy the equation) and thus it does not qualify as a "definition".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.