Tail recursion to while iteration in 2 easy steps

[rusi]

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.