Quicksort rewritten in tail-recursive form
An example using the Scala programming language I am currently learning Scala and I became quite intrigued by the compiler's ability to optimize tail-recursive calls. For those unfamiliar with the concept, a tail-recursive method can be optimized to be executed in constant stack space. This practically means that the recursion is not really necessary and that the method in question could be implemented as a simple iterative process! Nevertheless, it is nice to have the compiler do the trick of converting the recursion into a loop and let the programmers express their ideas using recursion. As an exercise, I set out to convert the renown Quicksort algorithm into tail-recursive form. But first, why would this algorithm need any conversion whatsoever? Let us see an implementation of the algorithm written in Scala. I am using the following piece of code as it appears in “Scala By Example” by Martin Odersky (draft of May 24, 2011). It is a straightforward implementation of Qui...