Easy Recursion: One Function, One Helper, One Global Variable

Just like Andrew said in his SLOG, when working on recursive code, it is often the case that simple instructions will not solve a problem. But what if I were to tell you that there is a simple way to achieve recursion? You would probably tell me I am lying, or otherwise say that I have probably broken Python (just like Dima told me when I mentioned I found a way). So what is the solution I found? It can be broken down into these elements:

• One Global Variable: Holds the information gathered by recursive code
• One Helper Function: Uses recursion to gather information into the global variable
• One Function: Clears the global variable, executes the helper function, and returns the global variable

Of course I would be penalized for efficiency, but bear in mind that this is an easy solution to what can seem a murky task to many. It uses recursion, yes, and it solves a problem, yes. Later on when you have more experience programming you can ditch this, but as a temporary solution, it should work great.

Let's put things into perspective. This is what we have seen in class:

def list_all(t):
    ''' (Tree) -> list

    Return list of values in t.

    >>> t = Tree(0)
    >>> list_all(t)
    [0]
    >>> t = descendents_from_list(Tree(0), [1, 2, 3, 4, 5, 6, 7], 3)
    >>> L = list_all(t)
    >>> L.sort()
    >>> L
    [0, 1, 2, 3, 4, 5, 6, 7]
    '''
    # implicit base case when len(t.children) == 0
    return [t.value] + gather_lists([list_all(c) for c in t.children])

(Credit to whoever did this code from Lab 05 solution)

This code is elegant, short, beautiful. It uses a helper function gather_lists(), which concatenates all sublists, and that is about it. The return line is only one line long. Now this will look like a travesty: I will do exactly the same, but using the method described before.

# Global variable here will hold all the info gathered
_all_elements = []

def list_all(t):
    ''' (Tree) -> list

    Return list of values in t.

    >>> t = Tree(0)
    >>> list_all(t)
    [0]
    >>> t = descendents_from_list(Tree(0), [1, 2, 3, 4, 5, 6, 7], 3)
    >>> L = list_all(t)
    >>> L.sort()
    >>> L
    [0, 1, 2, 3, 4, 5, 6, 7]
    '''

    # Clear the global variable first
    _all_elements.clear()

    # Call helper function
    _get_elements(t)
    
    # Return global variable
    return(_all_elements)
    
def _get_elements(t):
    ''' (Tree) -> None
    
    Gather all objects from the tree rooted at t in the global
    variable _get_elements
    '''
    
    # Append value to global variable
    _all_elements.append(t.value)
    
    # If there are children...
    if len(t.children) != 0:
        # Recursively work with the children
        for x in t.children:
            _get_elements(x)

So it does the same, but it is easier to understand, and easier to construct. It is also longer, less elegant, and probably not very efficient. It might be vulnerable to outside interference since it relies on using a global variables as a temporary vehicle.

Challenges

Recursion can be very challenging, but having a way to split the steps to visualize it better, while achieving results, can be encouraging. I encourage everyone to apply this method when unsure about what to do.

The challenge, hence, is how to get from this method to the more elegant, efficient one. And also the question on whether it consumes much more computation power than the elegant method. Perhaps it is not way better, but only slightly better.