What are the base cases in this recursive BST algorithm?

user_6396569 0
Viewed 64

I have not often written recursive functions/methods. I successfully understand the "base case" in simpler functions such as the following:

def countdown(num):
    if num == 0: # Base case
        return
    print(num) # Action
    countdown(num-1) # Reduction and recurse

def factorial(num):
    if num == 0 or num == 1: # Base cases
        return 1
    return factorial(num-1) * num # reduction + recurse + action

However, I have programmed an algorithm that finds the closest value to a given value in a Binary Search Tree (BST), as well as insertion, print all nodes, and other such algorithms. I've found these algorithms to be much harder to understand especially with regard to identify the base cases. This question specifically pertains to the following implementation of findClosest and _findClosest. Consider:

class BSTNode:
    def __init__(self,value=None):
        self.value = value
        self.leftChild = None
        self.rightChild = None

class BST:
    def __init__(self):
        self.root = None

    def findClosest(self, value):
        if self.root is None: # Base case 0
            print("There is no tree, so can't find closest!")
            return None
        else:
           return self._findClosest(value, self.root, self.root.value)

    def _findClosest(self, searchValue, currentNode, closest):
        if currentNode is None: # Base case #1
            return closest 
        if abs(currentNode.value - closest) < abs(closest - searchValue): # ACTION
            closest = currentNode.value
        if searchValue > currentNode.value: # Reduce and recurse
            return self._findClosest(searchValue,currentNode.rightChild, closest)
        elif searchValue < currentNode.value: # Reduce and recurse
            return self._findClosest(searchValue,currentNode.leftChild,closest)
        else:
            return currentNode.value # Base case #2

You can see that I attempted to identify the base cases. As I am using a sort of "driver, pseudo-public" method which handles the first base case of no root separately, I labeled that "base case 0". In any event, my point of confusion is that there are 4 separate return statements in _findClosest(), and my current knowledge of recusion would have me surmising that the two I've labeled Base case #1 and Base case #2 with comments are in fact the only two base cases in that method. However, in order for this method to work correctly, I've also had to return the results of _findClosest() when called on the leftChild and rightChild, so would these also be more base cases? I am having a difficult time determining what is a base case vs. what is the reduction/recursive step. The fact that there are multiple base cases and separate "paths of recursion" if you will, is far more difficult for me to understand than those simple recursive functions that I mentioned earlier. Finally, the base cases in the _findClosest method are also spread out, with the recursive calls sandwiched in the middle, further adding to my confusion.

Please note that the code provided runs fine on Python 3.7.9, however I purposely did not include the rest of the BST methods and driver as I was concerned with including too much code. I also am not sure that this questions would require those remaining items. If a suitable answer does, I will edit and add them.

binary-search-tree recursion algorithm python
2 Answers

For a recursive function, any state that doesn't require recursive computation can be a base case. Even if calculating the base value requires some computation (that isn't recursive), it qualifies as a base case, since it ends the recursion there.

Similarly, any statement that does or does not do any computation but makes a recursive call to some sub-state can be qualified as a recursive step (reduction depends on the computation; if the search space isn't reduced, you'll technically be stuck in infinite recursion).

As for your implementation, you've correctly classified the statements in _findClosest(). However, the classification for findClosest() wouldn't make much sense, since it isn't a recursive function anyways.

user_93507200

From

https://www.sparknotes.com/cs/recursion/whatisrecursion/section1/page/3/

The base case, or halting case, of a function is the problem that we know the answer to, that can be solved without any more recursive calls. The base case is what stops the recursion from continuing on forever. Every recursive function must have at least one base case (many functions have more than one).

When you are calling your recursive function _findClosest with left_child or right child, you are not sure if you find the the closest number of searchValue. You will be sure you found the closest number when one of the base case happen (currentNode is Null or currentNode.value == searchValue).

By the way, you could easily implement your function _findClosest as an iterative function (because you never let call of your function on the stack, '_findClosest' never called itself two time).

I think you made a mistake in the comparison, when you want to see if searchValue is closer with the currentNode.value then with the closest:

if abs(currentNode.value - closest) < abs(closest - searchValue):

should be:

if abs(currentNode.value - searchValue) < abs(closest - searchValue):

user_114146340
Related