Why You Should Avoid the Jargon Tail Recursion

By Xah Lee. Date:

Someone wrote: “iteration is Bad and tail recursion is Good”.

There are just too many spurious stupid jargons that's meaningless and endlessly confusing, yet embraced and spoke by all monkey coders. What i am coming into, is the jargon “tail recursion”. What a fantastically stupid meaningless term that is so loved by the programing geeks. In every trickle of chance they'll flash it out.

Now, let's talk about tail recursion.

I read the Structure and Interpretation of Computer Programs of Harold Abelson et al about 4 years ago. I recall reading the section on tail recursion. In particular, i recall how exacting and clear it explains the myths of looping away. To this day, i still hold their writing illuminating. (it is in reading their book, chapter i think 3 on functional dispatch, that it dawned on me what is OOP really about, far beyond any fantastically stupid OOP tutorials and books.) Abelson et al is quite lucid in explaining that the time/space algorithmic behaviors of those for/while/until loops of imperative languages can be equivalent to recursion. And, the term “tail recursion” means compilers that recognize recursion in source code that are iteration, and thus optimize it as iteration.

Kent Pitman wrote:

My point was that iteration means exactly what you said: to move down an object of unbounded length using finite space to perform each iteration. Tail recursion (but not real recursion) shares this property because tail recursion implements/expresses/is iteration.

Thanks Kent for this concise recapitulation.

As you described, some Scheme fanatics are mislead by Ableson's debunking of loop/recursion myth, to think that loop syntax should be avoided at all costs.

I believe this being plausible, or fact, and i think the culprit being: stupid terminology and jargons.

A quick look at the text on how the authors defined “tail recursion” found me:

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1

One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose “looping constructs” such as do, repeat, until, for, and while. The implementation of Scheme we shall consider in chapter 5 does not share this defect. It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive. With a tail-recursive implementation, iteration can be expressed using the ordinary procedure call mechanism, so that special iteration constructs are useful only as syntactic sugar.

From here we see the authors clearly indicated that the term “tail recursion” refers to a IMPLEMENTATION.

I think few people when they discuss “tail recursion” do have a clear idea that the phrase refers to a implementation. “Tail recursion” being a stupid jargon itself, thus confusion begets confusion, and there we have endless meaningless arguments and throwing of opinions with far-reaching consequences, not unlike the many jargons i have discussed in my previous post.

Imagine that people are info processors. In a newsgroup or general communication, people take muddy inputs from other people, process it with their imperfect processor, then express their output in a variety of muddy ways with these jargons galore. The process of “garbage in and garbage out” are nevertheless useful, since people are not exactly machines. But, imaging if we get rid of these stupid jargons and mis-representations and instead communicate on what we mean, what kind of percentage of stupidity we can get rid of society?

I propose that a part of those Scheme fanatics, where the Common Lispers accuse of being stupid tail-recursive purists, is in very large part due to the fantastic use and propagation of the term “tail recursion”. I propose, that we should ban the use of the term “tail recursion”. When refering to the concept of loop expressed in recursive form, simply say linear recursion. When refering to a good implementation of recursion that recognizes linear recursion, we simply should call it “good implementation” or perhaps “optimized implementation of linear recursion”. If this is achieved, i would say that the tail-recursive Scheme fanatics so accused would reduce in quantity significantly.

Next time you hear your colleague utter “tail recursion”, quickly grab a nearby book and whack his mouth. Look in his eyes, and say quizzically “do you mean optimized implementation of linear recursion?”. (if he says “What!?”, make a mental note that this guy didn't read Xah's opuses. Help him out. Resolve his mystery.)

my view is from English language and math perspective, in particular, as opposed to extraneous notions that's by-product of computer science. (For example, stacks, frames.)

so, from English perspective

the second is more clear and to the point, because it requires less context, less learning, to understand, and more precise. (to lisp programers, you may think the first one is simpler, but that's because you understand what the “tail” there means, and you understand “stacks”.)

from math perspective (here, math as Platonism, i.e. exist without human mind), there's the math concept of recursion, and of that concept, it can be classified into 2 types: linear and non-linear. Linear are those that can be easily re-expressed as a iteration, while the non-linear type cannot. (the exact detail can be easily formalized, i think) Therefore, from this perspective, the “tail call” isn't something about tail, it's about a particular kinda of recursion, and it can be easily optimized by machine. Therefore, from this perspective, the term “linear recursion” is also preferred. (note: the notion of computer engineering by-product of “stacks” is not necessary here.)

haha, that's one prolix reply. I'm in the mood. ☺

jargons and idioms are fun and loved, only by the people who understands them. Suppose, you are learning Chinese, and surely you are frustrated by the loads of incomprehensible idioms that clearly can be worded in a much simpler way but people just don't do it.

parts of the social function of jargons, is to keep outsiders out.

2003-06