How can I make the following function into a tail-recursive function?

3
votes

I was following along here and I was trying to get some practice into converting normal recursive functions into tail-recursive functions. I managed to understand the fibonacci and factorial versions but this one stumped me. I understand what the algorithm is doing and its the else statement that confused me in the conversion.

Inside the else, it tries to find a number that's closer to what you are looking for before giving up and going with the number it finds that is less than the one you suggest.

I am not sure how to write the helper function that makes this tail recursive. For the fibonacci and factorial, I ended up using an accumulator. Is there something similar that could be used here?

class BSTNode(object):
    """Binary search tree node."""

    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def __repr__(self):
        return '(%s, %r, %r)' % (self.val, self.left, self.right)

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

I understand that Python doesn't support the tail recursion optimization to allow constant stack space but I was just doing this for practice in Python as I like the syntax

2
pythonalgorithmrecursionbinary-treetail-recursion
It already is tail recursive. - thefourtheye
I thought that the function must be recursively called at the end to be considered tail-recursive or is this notion incorrect? - Cal
@thefourtheye: No, the right_best case isn't tail-recursive. - user2357112 supports Monica
@thefourtheye In order to make a function tail-recursive, the recursive call should be the last thing done (no instructions may come afterwards). - Nir Alfasi
@user2357112 Ah, right. I didn't look closer. - thefourtheye

2 Answers

3
votes

Instead of doing

if right_best is None:
    return bst.val

You can pass the best result found so far into the recursive call as an extra argument, and have the recursive call handle this check.

def find_val_or_next_smallest(bst, x, best=None):
    """
    Get the greatest value <= x in a binary search tree.
    Returns None if no such value can be found.
    """
    if bst is None:
        return best
    elif bst.val == x:
        return x
    elif bst.val > x:
        return find_val_or_next_smallest(bst.left, x, best)
    else:
        # bst.val is guaranteed to be the best yet, since if we had
        # seen a better value higher up, the recursion would have gone
        # the other way from that node
        return find_val_or_next_smallest(bst.right, x, bst.val)
2
votes

To Turn the function into tail-recursive you should carry the partial answer with you all the way by adding an extra parameter, val:

def find_val_or_next_smallest(bst, x, val=None):
    """
    Get the greatest value <= x in a binary search tree.
    Returns None if no such value can be found.
    """
    if bst is None:
        return val
    elif bst.val == x:
        val = x
    elif bst.val < x and (val is None or bst.val > val):
        val = bst.val

    if bst.val > x:
        return find_val_or_next_smallest(bst.left, x, val)
    else:
        return find_val_or_next_smallest(bst.right, x, val)

UPDATE

Having a tail recursion means that we can have an iterative solution (vs. recursive), and it can easily be demonstrated on the accepted answer - by converting it into an iterative solution:

def find_val_or_next_smallest(bst, x, val=None):
    """
    Get the greatest value <= x in a binary search tree.
    Returns None if no such value can be found.
    """
    while True:
        if bst is None:
            return val
        elif bst.val == x:
            return x
        elif bst.val > x:
            bst = bst.left
        else:
            val = bst.val
            bst = bst.right