Recursion and Helper Function

Question

Sorry if this is a general question but I am a beginner in Python and many times when I see other people code using recursion, they create a helper function for the main function and then call that helper function which itself is recursive.

This seems a bit different from the simplest cases of recursion for example (sum of lists, factorial) where the function only calls itself.

Can someone explain this technique more carefully perhaps with examples?

Much appreciated.

Example 1: (Reversing linked list using recursion)

def revert_list(self):
    self.head = self._revert_helper(self.head)


def _revert_helper(self, node):
    temp = None
    if node.forward == None: 
        return node
    else:
        temp = self._revert_helper(node.forward)
        node.forward.forward = node
        node.forward = None
    return temp

Example 2: (Binary Search Tree)

def __contains__(self, key):
    return self._bstSearch(self._root, key)

# Returns the value associated with the key.
def valueOf(self, key):
    node = self._bstSearch(self._root, key)
    assert node is not None, "Invalid may key."
    return node.value

# Helper method that recursively searches the tree for a target key:
# returns a reference to the Node. This allows 
# us to use the same helper method to implement
# both the contains and valueOf() methods of the Map class.

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

Answer 1

This is actually used more often in other languages, because python can usually emulate that behavior with optional arguments. The idea is that the recursion gets a number of initial arguments, that the user doesn't need to provide, which help keep track of the problem.

def sum(lst):
    return sumhelper(lst, 0)

def sumhelper(lst, acc):
    if lst:
        acc += lst[0]
        return sumhelper(lst[1:], acc)
    return acc

Here it's used to set a starting parameter to 0, so the user doesn't have to provide it. However, in python you can emulate it by making acc optional:

def sum(lst, acc=0):
    if lst:
        acc += lst[0]
        return sum(lst[1:], acc)
    return acc

Answer 2

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.

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.

Answer 3

From my experience (and my experience only), I use this style of coding when

1. The recursion is only useful in the larger function (not very recommended, but I have some bad habits)

2. There needs to be preparation done for the function, but only once (instead of a flag or other switch)

One way I use it is for logging purposes, while avoiding re-logging levels

def _factorial(x):
    return 1 if x == 0 else x*_factorial(x)

@log #assuming some logging decorator "log"
def factorial(x):
    return _factorial(x)

Otherwise, log would be called for each recursive level of the factorial function, something I may not desire.

Another usage would be to resolve default arguments.

def some_function(x = None):
    x = x or set() #or whatever else
    #some stuff
    return some_function()

Would check if x is falsey for every iteration, while what I actually need is a decorator, or as an alternative:

def some_function(x = None):
   return _some_function(x if x else set())

where _some_function is the helper function.

Specifically with 2, it allows for some freedom of abstraction. If for some reason you didn't want to use a bstsearch, you could just swap it for some other function in __contains__ (and you'd also be able to reuse code in different places)