'''
   20211017
   
   Robin Dawes
   
   This example was designed to show how recursion can give elegant solutions to problems that would be challenging to solve with 
   non-recursive methods.  While it is true that every problem than can be solved recursively can also be solved non-recursively,
   sometimes the recursive solution is much simpler and more intuitive.
   
   The problem to be solved here is "flattening" a list.  In Python, lists can contain other lists, which can contain still more lists, etc.   (In
   other words, lists can be nested, so [a, b, [c, [d, e], [f], g ] ] is a valid list.  We flatten a list by creating a new list containing all the same 
   values but without any nested lists.  The flattened form of the list just shown is [a, b, c, d, e, f, g].
   
   Think about solving this problem without recursion.  We could use a for loop to iterate through the top level of the list, and if any of those elements
   were a nested list we could use another for loop (inside the first one) to iterate through that list ... but what if there were another list inside that 
   one, and another inside that one, and so on?  We can't code infinitely many nested for loops.  We would have to set up some kind of clever book-keeping 
   arrangement to keep track of all the lists we were currently working on, and how far along we are in processing each one.  Whenever we finish a nested
   list we would need to go back to the list it was nested in and carry on where we left off.
   
   But using recursion, we can let Python take care of all the management details.  Making a recursive call automatically bookmarks where we are, and 
   when the recursive call ends we automatically go back to where we were.
   
'''
import random     # we will use the "sample" method 

# some single-element lists that we will randomly combine to build large, deeply nested lists.

list_1 = [1]
list_2 = ['a']
list_3 = [True]
list_4 = ["dragons"]
list_5 = ["Ursula"]


lists = [list_1, list_2, list_3, list_4, list_5]


for i in range(20):
   x, y = random.sample(range(5),2)        # Choose two integers from the range (0, 1, 2, 3, 4)
   lists[x].append(lists[y][:])                     # Use the integers to pick two of the lists, and 
                                                                  # append a copy of one to the end of the other

print("\n")
for l in lists:
   print(l)                                                   # let's see them

print("\n")
   
flat_list = []                                               # flat_list is a global variable.  We do not need to 
                                                                  # explicitly make it "global" in the function because
                                                                  # even though we append new values to it, we never
                                                                  # say "flat_list = ..." inside the function.

def flatten(thing):
   if type(thing) != list:                               # if the current thing is not a list, we just append it to
      flat_list.append(thing)                          # flat_list.  If it is a list, we make the recursive call on it
   else:                                                          
      for x in thing:
         flatten(x)
   
# This is quite remarkable!  In just 5 lines we have set up a function that will flatten any list, no matter
# how deep the nesting goes   (well, up to the limits of our computer's memory, anyway!) 
   
# Here it is in action on the randomly nested lists we created earlier   
flatten(lists)
print("\n")
print(flat_list)