Skip to content

Instantly share code, notes, and snippets.

@schoeke
Last active November 4, 2018 21:53
Show Gist options
  • Save schoeke/4eb39677b23ed8d4ad996f02b2b1ab34 to your computer and use it in GitHub Desktop.
Save schoeke/4eb39677b23ed8d4ad996f02b2b1ab34 to your computer and use it in GitHub Desktop.
Answer to a question on reddit on how to average nested lists of ints

This is a pretty complicated task, if you only just learned about recursion.

I will walk you through my thinking and then show you the code that I came up with.

Why recursion? Nested datatypes are hard to handle, especially if they can be arbitrarily nested. Recursion is a fine way of dealing with that.

What is this task similar to? Often, you can find a problem where you know the solution to and change that slightly. An average of a list of integers is the sum of the lists' elements divided by the length of the list. The length of the list is trivial, so what about the sum of a list? Easy! Iterate over the list and add the current element to the total. But nested lists?

Well, that's look at the cases. If you go for a recursive solution, you will need to think about the different cases you encounter. When you iterate over a nested list, you can encounter an element or a list. If you encounter an element, you already know what to do: Add it to the total. If you encounter a list, you will need run your recursive function on it. This looks something like this:

  def list_sum(given_list):
    total = 0
	  for element in given_list:
      # Check here if the element is of type list
		  if isinstance(element, list):
			  total = total + list_sum(element)
      # If not, just add it up.
		  else:
			  total = total + element
    return total

Notice that in the end, we return the total sum.

Now, the question is, how can we make this return the average instead? Obviously, we need to return the total divided by the length of the list. But can we just do that here? The answer is yes! Because we know the length of the given list. So, if you write return total/len(given_list), you are all done. Do not copy this blindly! Think about it for a second. Does this always work? Why? Walk through a few of your test inputs and see how it walks through the coe. What are the assumptions we have to make for the input?

Feel free to ask if you have any questions. HTH.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment