Understand recursion 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 &lt;= 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 &gt; 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.
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 &gt; x:
            return _inner(parent_node.left, x)
        else:
            right_branch.append(parent_node)
            return _inner(parent_node.right, x)
    return _inner(parent_node, x)