Tail-call optimization in recursive equations

Question

I have the following two mutually recursive functions,

Since Python doesn't handle tail-call optimization well, the programmer should represent these functions as stateful loops. What techniques does the Python community use to transform this kind of equation into explicit loops?

Or are these transformations algorithm-dependent and each recursive function must be analyzed separately?

Recursive implementation:

Let C1 = xpa, C2 = p and C3 = xpb then

def obaraSaika(p,s00x,i,j,xpa,xpb):

    if i < 0 or j < 0: return 0

    if i == 0 and j == 0: return s00x

    if i >= 1: return xpa*(obaraSaika(p,s00x,i-1,j,xpa,xpb)) + \
               p*((i-1)*(obaraSaika(p,s00x,i-2,j)) + j*(obaraSaika(p,s00x,i-1,j-1,xpa,xpb) ) )

    if j >= 1: return xpb*(obaraSaika(p,s00x,i-1,j,xpa,xpb)) + \
               p*(i * (obaraSaika(p,s00x,i-1,j-1)) + (j-1)*(obaraSaika(p,s00x,i,j-2,xpa,xpb) ) )

The idea of this implementation is to traverse the tree using firstly the i index, and then once i == 0, reduce the tree using the j index.

Answer 1

Transforming any recursive algorithm into a non-recursive equivalent is simple.

When you perform a recursive call, what you're actually doing is pushing a set of arguments onto a stack. This stack is provided to you by the Python interpreter.

So, the way you rewrite the algorithm without recursion is... you manage the stack yourself! When you would make a recursive call, instead you take all the arguments you would have passed and push them onto your stack object. Then you have a "driver" loop that repeatedly pops off the stack and does the computation listed therein.

The signature of this type of program is that there's one stack object, which you prime with an initial state tuple/object, and then a while len(stack) > 0 loop that runs until you're finished.

You basically do just what the recursion would do, but when you manage the relevant data structures yourself it gives you a better opportunity for efficiency gains.

This particular type of transformation works for any algorithm. Others, specifically those involving carrying global state across different calls to the function(s) in question, are algorithm-dependent.