Convert recursion to tail recursion

Question

I read about converting recursive algorithms into iterative algorithms. I came across a blog-post http://blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html explaining the procedure for converting recursive algorithms to tail recursive algorithms first and then converting the tail recursive to iterative The message explains that when we want to convert a recursive algorithm to a tail recursive one, we must first understand what happens between return of the recursive callandreturn statement of the calling function.. Once this is done, we should try to add the secret function / battery parameters for the recursive function, and then decide what to return. I adhered to the concept of examples provided in the blog, but I can not solve this problem at the end of the blog. I can’t decide what should be my battery setting? How should I make decisions based on this battery setting. I do not want a solution, but some recommendations on how I should think in order to solve this problem. Here is the exercise code:

def find_val_or_next_smallest(bst, x):
    """Get the greatest value <= x in a binary search tree.

    Returns None if no such value can be found.

"""
    if bst is None:
        return None
    elif bst.val == x:
        return x
    elif bst.val > x:
        return find_val_or_next_smallest(bst.left, x)
    else:
        right_best = find_val_or_next_smallest(bst.right, x)
        if right_best is None:
            return bst.val
        return right_best 

Thanks in advance!

Answer 1

I am posting this to replace my comments from yesterday and show the code.

, . . , . .

. .

. docstring elif return if ( ).

def find_val_or_next_smallest1(bst, x):
    if bst is None:
        return None
    if bst.val == x:
        return x
    if bst.val > x:
        return find_val_or_next_smallest1(bst.left, x)
    else:
        right_best = find_val_or_next_smallest1(bst.right, x)
        if right_best is None:
            return bst.val
        return right_best

---

. . , :

    right_best = find_val_or_next_smallest1(bst.right, x)
    if right_best is None:
        return bst.val
    return right_best

bst.val, , , . , bst.val . " , ". "return None, ". None. found, , .

def find_val_or_next_smallest2(bst, x, found=None):
    if bst is None:
        return found
    if bst.val == x:
        return x
    if bst.val > x:
        return find_val_or_next_smallest2(bst.left, x, found)
    else:
        return find_val_or_next_smallest2(bst.right, x, found=bst.val)

---

, :

def find_val_or_next_smallest3(bst, x, found=None):
    while True:
        if bst is None:
            return found
        if bst.val == x:
            return x
        if bst.val > x:
            bst, x, found =  bst.left, x, found
        else:
            bst, x, found =  bst.right, x, bst.val

:

def find_val_or_next_smallest4(bst, x):
    found=None
    while True:
        if bst is None:
            return found
        if bst.val == x:
            return x
        if bst.val > x:
            bst = bst.left
        else:
            bst, found = bst.right, bst.val