How can I make the following function in a tail recursive function?
I followed here and I was trying to get some practice in converting normal recursive functions to tail-recursive functions. I was able to understand fibonacci and factorial versions, but this alarmed me. I understand what the algorithm is doing and its else statement that confused me on the conversion.
Inside the else, it tries to find a number that is closer to what you are looking for, before giving up and finding the number it finds that is less than the one you suggest.
I'm not sure how to write a helper function that makes this tail recursive. For fibonacci and factorial, I ended up using the battery. Is there something like this that can 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 does not support tail recursion optimizations to allow constant stack space, but I was just doing it for practice in Python as I like the syntax
source to share
Instead of doing
if right_best is None:
return bst.val
You can pass the best result you have found so far to the recursive call as an additional argument and handle that recursive call.
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)
source to share
To turn a function into tail recursion, you have to completely wrap the partial answer 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 tail recursion means that we can have an iterative solution (versus recursive), and it can be easily demonstrated in the accepted answer - by converting it to 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
source to share