Tail Recursion considered harmful?

Some time back, someone told me that tail recursion is a lot like using a 'goto' this makes a lot of sense when you think about it. Tail recursion is an optimization that can happen when a function is calling itself as and returning the result as it's return. This allows the system to skip creating a new frame on the stack and makes life a little easier when fiddling with limited stack while doing embedded work.

An example might help:

So the code compiles and both do what it looks like they do. What's the big deal? And isn't 'goto' bad?  Everyone knows it right? What about that famous paper and everything.  It sure looks like recursion is just a fancy way to do a goto.

Lets dig into it a little:

First we should look at the paper... more than just the title of course but first we can focus on the title.  Kind of an interesting thing happened with the title.  The writer of the paper did not chose it the editor of the publishing journal did. Turns out the original title was "A case against the goto statement."

To the editor, this title was not quite right so he changed it to: "Go To Statement Considered Harmful." Sounds like clickbait to me. Oh, wait, it is. Turns out that way before 'clickbait' was a thing people had to sell the news (that is convince people to part with hard earned money for a physical paper, how quaint.)

According to my hastily googled up source; 1949 gave us this: "Rent Control Controversy / Enacting Now of Hasty Legislation Considered Harmful" sounds exciting right? That is from the national news.  It looks like the "Go To" title started a bit of a theme in CS articles: "Global variables considered harmful" and "The letter O considered harmful."

Global variables I can see, and wish that the message got out more on that, but really, the letter O? (Let me tell you it was a real problem, 0 and O didn't always look so different. In fact my typewriter doesn't even have a zero, gotta use the O to make a zero so yeah the problem is real.  See also l and 1 bet you have to squint to figure out which is 'ell' and which is 'one', 1 would tell you but 1 already forgot. (Are we sure computers use Ones and Zeros or do they use Ohs and Ells?))

If Dijkstra's title is where you stopped reading, you better try again... wait if you stopped at Dijkstra's title how did you get this far in this silly little blog post?  Doesn't matter!  Go read the rest of Dijkstra's article it is only a few pages:

https://www.cs.utexas.edu/users/EWD/ewd02xx/EWD215.PDF

Hmm, interesting.  That was published in 1968 in case you missed that detail.  They sure knew a lot back then. 

What I got from it is the article is that Goto causes serious issues with being able to tell how we got to where we are in a program. We call a stack trace now but only because we can walk the stack and know there wasn't any funny business. 

My little trick above is a bit of an illusion.  When you start allowing stuff like that people become a little immune to goto and will let it slip in other places, then pandemonium.

I was wondering what it would be like if the paper had retained it's original title. Would it have gained traction and would goto have been effectively banished as it is today? We may never know unless we were able to shift into the parallel universe where it was not banned.

Well, I traveled to that parallel universe.  There are companies that run custom home grown software written in BASIC.  Yes, that BASIC:

10 print "hello world"

20 goto 10

Yes, THAT BASIC.  I took on some work there and let me tell you it sure was interesting.  On one hand BASIC grew in the last many years since I learned it first and the flavor they are using has some features that effectively allow you to not use that basic. The client didn't get the message.  So yes, if the title had remained "A case against the goto statement.", we might all have been doomed to live in this weird parallel universe.

Who was the masked stranger that saved us all from certain doom? No mask and not a stranger it is Niklaus Wirth. (Europeans call him by name, Americans by value (his joke, not mine))

If you have not heard of him, please look him up.  He was instrumental in creating Pascal, Modula, Oberon programming languages.  Also EBNF can be traced back to him along with "Railroad Diagrams" (aka Syntax Diagrams)

Is Goto harmful? 

Maybe, maybe not. Did Dijkstra formulate a case against it, yes I think definitely.  Goto is going to be there at a low level but hidden away by tools of a more civilised age.

Is Tail Recursion harmful?

I think that is the wrong question.  I think the real question is: Is Tail Recursion the same as using a Goto?  Which I think the answer is no. Earlier today I thought maybe they were the same, after thinking and reading Dijkstra's article again which calls recursion in place of goto I am more convinced that goto can go.

Gotos replacing tail recursion are a gateway to mass hysteria. Gotos everywhere, jumping into the middle of a function with no way to know how you got there or where you came from.  Sounds like I am exaggerating, maybe I am, but not by much (been there and done that it's not pretty.)


Links to more on this:
https://en.wikipedia.org/wiki/Considered_harmful
https://en.wikipedia.org/wiki/Niklaus_Wirth
https://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_form
https://en.wikipedia.org/wiki/Syntax_diagram

What I find most interesting about this is the link between Dijkstra and Wirth, not something I usually think about. Nobody works in a vacuum and this is one instance that highlights the collaboration in an interesting way. 

It really is fun looking into some of the history behind what we do. With the history so recent I wonder why it is not purposefully studied more.

One last thing:

I had trouble deciding on the title for this the alternate is

"Considered Harmful" Considered Harmful  ... see what I did there?  A little recursion in the title.  Let me know in the comments which title you would have picked.


You can also read about this here: Tail Recursion considered harmful?