Understand recursion

Question

I'm trying to improve my understanding of recursive and iterative processes. I've started with SICP, but have branched off to try and find a few exercises when I started having difficulty. Currently I've been looking at a series of posts on the subject by Tom Moertel.

Tom's code defines a node object for binary search trees and a search function:

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

The exercise asks us to transform the search function into an iterative process and gives a general procedure for doing so: refactor all recursive calls into tail calls using accumulators and then create a loop structure.

I've refactored the else clause in the search function into:

    else:
        return work(find_val4(bst.right, x), bst)

def work(child_node, parent_node):
    if child_node is None:
        return parent_node.val
    return child_node

But I've been having trouble figuring out how to move the logic done in the 'work' function into an accumulator. Any advice, hints, or ways to think about this would be totally appreciated.

Answer 1

Ahhhh. Okay.

That the issue here is that if the process takes a right branch at node Foo, it needs to store a reference to Foo in the event that it fails to find a child node which is less-than or equal. That reference effectively lives in the stack-calls which occur in inside the calls to the work function.

There can be an arbitrary number of these calls, so we need an internal, private stack:

def find_val_iterative(parent_node, x):
    right_branch = []
    def _inner(parent_node, x):
        if parent_node is None:
            if right_branch:
                return right_branch.pop().val
            return None
        elif parent_node.val == x:
            return x
        elif parent_node.val > x:
            return _inner(parent_node.left, x)
        else:
            right_branch.append(parent_node)
            return _inner(parent_node.right, x)
    return _inner(parent_node, x)