- 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)  >>> 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)  >>> 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.
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.