There's a book out there, can't remember which; that has two index entries for recursion, both referring to the other. I always thought it was a nice touch.

K&R, The C Programming Language, does this. There may be others but this is where I first saw it and a quick google search confirmed it.

I like this version:

In order to understand recursion, you must first understand recursion.

I never found that joke particularly clever because it misses the significance of having a base case. So it’s just about infinite loops. Is there a version of it that includes a base case?

Indeed, the joke seems to be more appropriate for something like “In order to understand circular reasoning, you must first understand circular reasoning.”

The base case is understanding the joke

If you don’t yet understand recursion, you must first understand recursion.