Chris Angelico <[email protected]>: >> def quicksort(array, start, end): >> midp = partition(array, start, end) >> if midp <= (start+end)//2: >> quicksort(array, start, midp) >> quicksort(array, midp+1, end) >> else: >> quicksort(array, midp+1, end) >> quicksort(array, start, midp) > [...] > That's a prime example of recursion... but not of recursion that can > be tail-call optimized into iteration.
Of course it can. The 2nd and 4th calls to quicksort can be trivially tail-call-optimized. Tail-call optimization has nothing to do with converting algorithms into iterations. It's a prosaic trick of dropping an unneeded stack frame before making a function call. > The claim that TCO means you don't need stack space for all those > levels of recursion doesn't work if you still need stack space for all > those levels of recursion *before* you get to the tail call. Nobody is making that claim. What you are questioning is what tail-call optimization would buy you in practice. Not much. The few times you run into a stack overflow, you can refactor your code pretty easily. However, when you have to do that, it feels a bit silly. Marko -- https://mail.python.org/mailman/listinfo/python-list
