In Hofstadter's Gödel, Escher, Bach: An Eternal Golden Braid (GEB), the following claim appears:

...in the species Felis catus, deep probing has revealed that it is indeed possible to read the phenotype directly off the genotype. The reader will perhaps better appreciate this remarkable fact after directly examining the following typical section of the DNA of Felis catus:
...CATCATCATCATCATCATCAT...(OP note: truncated because, you get it)

Is this true? A cursory search for the DNA of Felis catus gives me this 1996 paper by Lopez, Cevario, and O'Brien and the given sequence does not appear – there are some instances of "CAT" but not repeated enough to make it as remarkable as claimed in GEB.
I don't know enough Biology to judge the veracity of this claim. Some points I am considering are:

GEB is full of wordplays. However, the tone of this part of the text does not sound like one to me.
GEB was written/published around 1978. The paper I linked to – which was cited by some 236 others according to Google – was published in 1996, way after GEB's time. If my impression that Lopez et al.'s work is significant because it is the first time Felis catus has been sequenced, then there is no way Hofstadter could've known of it when he wrote GEB. Then again, I don't know enough Biology that there might be some nuance to Lopez et al.'s paper that I'm missing (i.e., the results of the paper might not be mutually exclusive to the claim made in GEB).
GEB has reference notes and bibliography and there is no reference cited to back this claim. However, GEB does not attempt to be a rigorous academic thesis and the references is only called upon more when Hofstadter quotes other works directly while the bibliography is a list of readings which the reader may want to check out, regarding the main thesis of the book.

So are cats recursions with no base cases?

The Felis catus genome has been published, annotated, and updated quite a bit since 1996, including spans of so-called intergenic regions, which are basically scaffolding and other structures, along with perhaps some unidentified genes, pseudogenes, regulatory sequences, etc. Basically, pretty much the entire DNA sequence is available now, not just the gene sequence of the mitochondrial genome, which was what was published in the 1996 paper you referenced. Mitochondria are the power plants of the cell, but are just an organelle that happens to contain its own DNA; they are separate from the chromosomal DNA in the nucleus. All of this is available for free (if you know where to look) at the National Center for Biotechnology Information (NCBI), part of the National Library of Medicine (NLM) at the National Institutes of Health (NIH) in the United States. Other sites are also available, such as Ensembl, a joint project between the European Bioinformatics Institute (EMBL-EBI), part of the European Molecular Biology Laboratory (EMBL), and the Wellcome Trust Sanger Institute (WTSI). Both institutes are located on the Wellcome Trust Genome Campus in the United Kingdom.
So, to the genome. Genomic sequences can be searched in a couple of different ways, depending on what you're looking for, but the most common way is to use BLAST, the Basic Local Alignment and Search Tool. As the name implies, it takes sequences as input and searches one against the other, aligning the results as best as possible using certain algorithms that the user can define and tweak. The BLAST web interface to the cat genome is here. You don't need to worry about any of the other options here except the "Enter Query Sequence" box. FASTA format is just using the single-letter abbreviations for nucleotides (AGCT), all strung together.
The genome we're searching is of an Abyssinian cat named Cinnamon:

Cinnamon, the cat which was chosen to be the definitive genetic model for all cats in the feline genome project. Image courtesy of the College of Veterinary Medicine at the University of Missouri.
To start with, I typed in CATCATCATCAT and to my surprise got back over 200 hits, covering every chromosome the cat has. So, I doubled the length of the input to 8 CATs, and got back the same result set. Unfortunately, 12 CATs was too many (and really, it is too many), so I worked backwards.
The final results are here (sorry, link expires 10/13/16. To regenerate, go to BLAST link above and enter CATCATCATCATCATCATCATCATCATCAT). Apparently, popular wisdom is incorrect, and Felis catus chromosomes really contain 10 CATs each, one more than is needed for their 9 lives. No word yet as to why this may be, but scientists are presumably working on it.
