Tail recursion to while iteration in 2 easy steps
rusi
rustompmody at gmail.com
Wed Oct 2 09:29:39 EDT 2013
On Wednesday, October 2, 2013 1:53:46 PM UTC+5:30, Alain Ketterlin wrote:
> rusi writes:
>
>
>
> > On Wednesday, October 2, 2013 3:00:41 AM UTC+5:30, Terry Reedy wrote:
> >> Part of the reason that Python does not do tail call optimization is
> >> that turning tail recursion into while iteration is almost trivial, once
> >> you know the secret of the two easy steps. Here it is.
>
> >
> > What happens for mutual tail recursive code like this
> >
> > def isodd(x) : return False if x==0 else iseven(x-1)
> > def iseven(x): return True if x==0 else isodd(x-1)
>
>
> It takes one step of inlining to make Terry's technique applicable.
Well I did say my example was trivial!
For a more nontrivial case consider the delta function of an FSM.
The cleanest way of doing it in C is to make one function with a goto label for each state and a goto for each transition
The same thing can be done in a TR optimized language like scheme by making each state into a function and each transition into a TR-call
>
>
>
> (Actually, out of curiosity, I tried this with gcc 4.6.3: the compiler
> does 16 levels of inlining, plus tail call optimization. The final code
> has no call.)
Good to know.
More information about the Python-list
mailing list