Recursion that isn’t

Joey’s recent post reminded me of the old joke about an entry in a dictionary:

recursion see recursion

Non-geeks can stop reading here: if you didn’t understand the joke, you won’t understand what’s coming next either.

I mean, sure it’s a funny joke, but it doesn’t quite work. Technically, it’s not even an example of recursion, as the base case is missing. Perhaps it’s co-recursion? — but it isn’t, as it’s not progressing.

Why can’t we say instead,

recursion if you do not understand it, see recursion

It would still be funny, and it might actually work.

8 thoughts on “Recursion that isn’t

  1. I’ve never liked that joke either, for the same reason. Let’s hope
    your alternate suggestion catches on.

    Co-recursion I’ve never heard of, but wikipedia has; well, that’s
    incomprehensible. Infinite data structures? Is this something
    that can be done in C, or only in weird languages like Haskell?

    Ah, recursion is an old favorite, but it brings to mind the Apple ][
    where the stack was fixed at 256 bytes so you had to be careful
    not to recurse too deeply, and you had hard-to-find problems where
    you could call certain subroutines from most places but not from
    others… those were the days, not entirely missed.

    Dave

  2. I wasn’t aware that recursion required a base case. Isn’t this function recursive:

    void recurse() {
    recurse();
    }

    It dosn’t have any base case (which makes it for infinite recursion).

  3. Here’s the definition of corecursion:

    corecursion: tell somebody what corecursion is, then see corecursion

  4. This word: recursion. I don’t think it means what you think it means.

    A definition is recursive if it refers to itself in its own definition. That is the only requirement. The original joke is most certainly recursive. Would you claim that the haskell expression “ones = 1 : ones” is not recursion because there is no base case?

    What you are talking about is induction (ala proof-by-induction), which is often implemented in terms of recursion. This requires a base case and an inductive case.

  5. On reflection, Justin, I believe you are right that I was wrong about some of the things I said above. A the same time, you are wrong about some of the things you said. I’ll write a separate blog post about recursion shortly.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>