You can do QuickSort without *any* recursion…but then you have to explicitly manage a stack for bookkeeping purposes. I would hesitate to call any function that uses two recursions to be “tail-recursive”, but perhaps that’s a matter of taste. Finally, the best environment for QuickSort is a language that has mutable arrays - in which case QuickSort can be done easily in-place. Add in a stack data type, and you don’t need recursion. Dig back into ancient texts (as in, the 1960’s) to find many examples. I recall implementing it in assembler, without any language support for recursion. In more modern times, it is convenient to present QuickSort in recursive form. I’m not at all sure that it’s worthwhile to START with the recursive form and then hack away at it to remove recursions that are too expensive. Better would be to use a language where recursion is NOT expensive. If you are going to use recursion, and can’t do things in-place, then MergeSort is a better choice. MergeSort canNOT be done in place. Plus, MergeSort has better THEORETICAL properties (if not in practice) than QuickSort. Finally, for many geometric operations, you may find that the list to be sorted is already “almost sorted”. In that case, InsertionSort may be faster than either MergeSort or QuickSort. If you can write an efficient InsertionSort, you may find that it is the best choice for actual cases (as opposed to fully random test cases). Well…one more… in a multi-threaded environment, MergeSort can be a disaster, because it may spawn many, many sub-threads. QuickSort is better behaved in this respect. InsertionSort gets no help whatsoever from multi-threading. -- Kenneth Sloan KennethRSloan@gmail.com Vision is the art of seeing what is invisible to others. > On Apr 12, 2016, at 01:54 , Ronaldo <rcmpersiano@gmail.com> wrote: > > So, the code of qs() uses tail recursion for the higher part and regular > recursion for the lower one. This agrees with some quicksort schemes I found > where they use "while" iteration instead of one of the recursions. Usually > the method iterates over the smaller partition. In qs(), I replaced the > iteration by a tail recursion. > > I don't see how to implement in OpenSCAD language the full scheme where the > iteration (or tail recursion) operates over the smaller partition. If a > let() was allowed in tail recursion... it might be possible. > > > > -- > View this message in context: http://forum.openscad.org/Tail-recursion-tp17040p17061.html > Sent from the OpenSCAD mailing list archive at Nabble.com. > > _______________________________________________ > OpenSCAD mailing list > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org