the blog for developers

This Function is Not Tail Recursive

Tail recursion seems to be an easy concept, but most people get it wrong – including me. Reading the latest German Java SPEKTRUM, I’ve found an article about parallel multicore development by Kornelius Fuhrer. One paragraph was about functional development and tail recursion. First he claims tail recursion makes functions 100% parallizeable (I guess broadly speaking all compositions h(g,f) of side effect free functions g,f are 100% parallizeable in f and g, nothing to do with tail recursion) then he claims his example functions are tail recursive:

Wikipedia says about tail recursion:

In computer science, tail recursion (or tail-end recursion) is a special case of recursion in which any last operation performed by the function is a recursive call, the tail call, or returns a (usually simple) value without recursion.

In all three examples the last operation performed is the multiplication (*), not the function call to itself. First the function itself is called, then the return value is multiplied by n. Stackoverflow has a lot to say about tail recursion too.

A tail recursive version of factorial might look like this:

So please, do not call all functions where the last function call in your source code is a call to itself, tail recursive. A function is tail recursive, if the last operation is a function call to itself.

About the author

stephan Stephan Schmidt has been working with internet technologies for the last 20 years. He was head of development, consultant and CTO and is a speaker, author and blog writer. He specializes in organizing and optimizing software development helping companies by increasing productivity with lean software development and agile methodologies. Want to know more? All views are only his own. You can find him on Google +

Discuss on Hacker News Vote on HN