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.