sobota, 11 października 2014

You need to know: tail end recursion

A few years ago I did a small quasi-prepared-Kata exercise to demonstrate differences between programming in (and thinking in) different programming languages. I chose a simple state machine as an example and implemented it in Common Lisp, Java and C.

Having programmed in each of these languages at some point in my life, I deliberatly used approach typical for each of the languages. I even exaggerated a little to emphasize the characteristics of languages and how they influence our thinking. For example, I used a little more than needed classes and objects in Java and avoided recursion, whereas in Common Lisp, the state machine was transitioning from one state to another by a recursive tail call.

One of the observers questioned the Lisp implementation saying that it would quickly result in stack overflow. Although I intuitively felt that was not true, I was not able to explain why. Right after that session, I searched for information about recursion in functional languages and I learned about tail end recursion. A nice summary is given here: http://en.wikipedia.org/wiki/Tail_call

I recommend reading this Wikipedia entry, it explains really well things that are often not known by programmers focused on imperative languages.

Brak komentarzy:

Prześlij komentarz