Path: csiph.com!optima2.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!1.eu.feeder.erje.net!eternal-september.org!feeder.eternal-september.org!mx02.eternal-september.org!.POSTED!not-for-mail From: Marko Rauhamaa Newsgroups: comp.lang.python Subject: Re: Possibly Pythonic Tail Call Optimization (TCO/TRE) Date: Tue, 14 Jul 2015 08:41:37 +0300 Organization: A noiseless patient Spider Lines: 34 Message-ID: <87bnffnvn2.fsf@elektro.pacujo.net> References: <55A3A853.4040006@rece.vub.ac.be> <55A3C366.6060602@rece.vub.ac.be> <87fv4r1fre.fsf@jester.gateway.sonic.net> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: mx02.eternal-september.org; posting-host="b7cb1518d23ec19d482dcc9c31d30fdd"; logging-data="30795"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX198I96hX6YAXjx/Iezfoq9L" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) Cancel-Lock: sha1:p3o+r8Dd8RhqeVwqucVvpiRCdCQ= sha1:4r3krgUU6T7qejf2bfM/okRwwj8= Xref: csiph.com comp.lang.python:93785 Chris Angelico : >> 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