Return to Answer

EDIT: Okay, discussion of your examples.

• Example 1: (Reversing linked list using recursion)

Pretty simple: the "helper" function is a general recursive function that will work on any node in the class that has a linked list. Then the wrapper is a method function that knows how to find self.head, the head of the list. This "helper" is a class member function, but it could also be a simple function in a general data-structures stuff library. (This makes more sense in Python than in languages like C, because a function like this could work with any linked list that is a class with a member called forward as its "next pointer" value. So you really could write this once and then use it with multiple classes that implement linked lists.)

• Example 2: (Binary Search Tree)

The actual recursive function returns None if no node can be found with the specified key. Then there are two wrappers: one that implements __contains__(), which works just fine if it returns None; and valueOf(), which raises an exception if the key is not found. As the comment notes, two wrappers lets us solve two different problems with a single recursive function.

Also, just as with the first example, the two wrappers kick off the search in a specific location: self._root, the root of the tree. The actual recursive function can be started anywhere inside a tree.

If __contains__() were implemented with a default argument of a node to search, and the default was set to some unique value, it could check for the special value and start at the root in that case. Then when __contains__() is called normally, the unique value would be passed in, and the recursive function could know that it needs to look at the special location self._root. (You can't just pass in self._root as the default value, because the default value is set at compile time, and the class instance can change after that, so it wouldn't work right.)

class UniqueValue:
    pass

def __contains__(self, key, subtree=UniqueValue):
    if subtree is UniqueValue:
        subtree = self._root

    if subtree is None:  # base case
        return None
    elif key < subtree.key: # target is left of the subtree root
        return self.__contains__(key, subtree.left) 
    elif key > subtree.key: # target is right of the subtree root
        return self.__contains__(key, subtree.right) 
    else:                      # base case
        return subtree

Note that while I said it could be implemented as I show here, I didn't say I prefer it. Actually I prefer the two wrappers version. This is a little bit tricky, and it wastes time on every recursive call checking to see if subtree is UniqueValue. More complex and wastes time... not a win! Just write the two wrappers, which start it off in the right place. Simple.

Usually when I do this, it is because the recursive function is tricky or annoying to call, so I have a wrapper that is more convenient. For example, imagine a maze solver function. The recursive function needs a data structure to keep track of visited spots inside the maze, but for convenience to the caller I just want the caller to need to pass in a maze to solve. You can maybe handle this with a default variable in Python.

The other major reason I have done this is for speed. The recursive function is very trusting, and assumes its arguments are all valid; it just goes full speed ahead with the recursion. Then the wrapper function carefully checks all the arguments before making the first call to the recursive function. As a trivial example, factorial:

def _fact(n):
    if n == 1:   # still need to handle the basis case
        return n
    return n*_fact(n-1)

def fact(n):
    if n <= 0: # check for invalid argument
        return 0
    return _fact(n)

Usually people wouldn't bother with this two-function solution for something as simple as checking that the argument isn't negative. And for factorial, you still need to check for the basis case so the recursion stops, so there really isn't much point to writing it the way I did above!

I could give less vague answers if you posted an example you have seen of code that inspired this question.

Usually when I do this, it is because the recursive function is tricky or annoying to call, so I have a wrapper that is more convenient. For example, imagine a maze solver function. The recursive function needs a data structure to keep track of visited spots inside the maze, but for convenience to the caller I just want the caller to need to pass in a maze to solve. You can maybe handle this with a default variable in Python.

The other major reason I have done this is for speed. The recursive function is very trusting, and assumes its arguments are all valid; it just goes full speed ahead with the recursion. Then the wrapper function carefully checks all the arguments before making the first call to the recursive function. As a trivial example, factorial:

def _fact(n):
    if n == 0:   # still need to handle the basis case
        return 1
    return n*_fact(n-1)

def fact(n):
    n0 = int(n)
    if n0 != n:
        raise ValueError("argument must make sense as an int")
    if n < 0:
        raise ValueError("negative numbers not allowed")
    return _fact(n)

I have edited this from the original, and now it's actually a pretty reasonable example. We coerce the argument to an integer ("duck typing") but we require that the != operator not indicate it to have changed in value by this coercion; if converting it to int changes the value (for example, a float value that had a fractional part truncated) we reject the argument. Likewise, we check for negative and reject the argument. Then the actual recursive function is very trusting and contains no checks at all.

I could give less vague answers if you posted an example you have seen of code that inspired this question.

Usually when I do this, it is because the recursive function is tricky or annoying to call, so I have a wrapper that is more convenient. For example, imagine a maze solver function. The recursive function needs a data structure to keep track of visited spots inside the maze, but for convenience to the caller I just want the caller to need to pass in a maze to solve. You can maybe handle this with a default variable in Python.

The other major reason I have done this is for speed. The recursive function is very trusting, and assumes its arguments are all valid; it just goes full speed ahead with the recursion. Then the wrapper function carefully checks all the arguments before making the first call to the recursive function. As a trivial example, factorial:

def _fact(n):
    return n*_fact(n-1)

def fact(n):
    if n <= 0:
        return 0
    return _fact(n)

Usually people wouldn't bother with this two-function solution for something as simple as checking that the argument isn't negative.

I could give less vague answers if you posted an example you have seen of code that inspired this question.

Usually when I do this, it is because the recursive function is tricky or annoying to call, so I have a wrapper that is more convenient. For example, imagine a maze solver function. The recursive function needs a data structure to keep track of visited spots inside the maze, but for convenience to the caller I just want the caller to need to pass in a maze to solve. You can maybe handle this with a default variable in Python.

The other major reason I have done this is for speed. The recursive function is very trusting, and assumes its arguments are all valid; it just goes full speed ahead with the recursion. Then the wrapper function carefully checks all the arguments before making the first call to the recursive function. As a trivial example, factorial:

def _fact(n):
    if n == 1:   # still need to handle the basis case
        return n
    return n*_fact(n-1)

def fact(n):
    if n <= 0: # check for invalid argument
        return 0
    return _fact(n)

Usually people wouldn't bother with this two-function solution for something as simple as checking that the argument isn't negative. And for factorial, you still need to check for the basis case so the recursion stops, so there really isn't much point to writing it the way I did above!

I could give less vague answers if you posted an example you have seen of code that inspired this question.