I would like to learn whether the following recursive code can be made more efficient by an iterative implementation, and if so, how such implementation can be done. It has been some years since I have actively coded, so I have forgot enough nomenclature that I don’t think I can answer this question myself with the help of existing literature.

Denote by land r the number of left and right turns we have taken in a binary tree of height n. Suppose that f(l, r) is some real function that computes some value depending on l and r in constant time. Assume that f is not symmetric, i.e. not necessarily f(l,r) = f(r,l). The recursive code is as follows (in Python 3):

def recursive_travel(l, r, cur_height, max_height):
    if cur_height == max_height:
       return f(l, r) * (f(l+1, r) + f(l, r+1))
    return recursive_travel(l+1, r, cur_height+1, max_height) + recursive_travel(l, r+1, cur_height+1, max_height)

and the initial call should be recursive_travel(0,0,0,n). Iterative implementation will be a slightly more faster without the need for recursive calls, but I don’t know whether there is an elegant way to implement this. All help will be appreciated!