D. concat(L1, L2): returns a mylist that is a concatenation of L1 and L2.

From EECS 182
D. concat(L1, L2): returns a mylist that is a concatenation of L1 and L2.
Jump to: navigation, search
 
Line 24: Line 24:
 
         result = L1withL2part.append(L2.last())
 
         result = L1withL2part.append(L2.last())
 
         return result
 
         return result
 +
 +
 +
Q: What if you tried to do recursion on L1? We can try that and see what happens:
 +
 +
* Base case: L1 is empty: the answer is L2.
 +
* Non-base case: Let's split L1 into L1.pop() and L1.last(). Can we create the final answer using concat and other available functions using L1.pop(), L1.last(), and L2?  May be if we can somehow get L1.last() added at the front of L2, we could do it. Then, the answer would be concat(L1.pop(), L1.last() added to the front of L2). But, do we have a way to add L1.last() at the front of L2?  Not so far. We would have to write another function to do that, say insert_first(element, L). If that was available, the solution would be:
 +
 +
def concat(L1, L2):
 +
      if (L1.isempty()):
 +
            return L2
 +
      else:
 +
            L1lastwithL2 = insert_first(L1.last(), L2)
 +
            return concat(L1.pop(), L1lastwithL2)
 +
 +
Clearly, doing recursion on L2 is easier here because the 2nd one requires us to write another function insert_first. Of course, there is an exercise here on how to do that. So, 2nd approach is also viable.

Latest revision as of 17:58, December 15, 2011

Returns the concatenation of two lists. Best to solve recursively. Why? Because the answer is easy to compute if one of the lists is empty (it will be the other list.). Given that it is easier to stick elements at the end using the append method, let's first try recursing on L2.

Solution:

def concat(L1, L2):
   if (L2.isempty()):
       return L1
   else:
       return concat(L1, L2.pop()).append(L2.last())

Other solutions:

def concat(L1, L2):
   if (L2.isempty()):
       return L1
   else:
       L2part = L2.pop()
       L1withL2part = concat(L1, L2part)   # put together L1 and L2part. Recursive step. Just assume it works.
       result = L1withL2part.append(L2.last())
       return result


Q: What if you tried to do recursion on L1? We can try that and see what happens:

def concat(L1, L2):
      if (L1.isempty()):
            return L2
      else:
           L1lastwithL2 = insert_first(L1.last(), L2)
           return concat(L1.pop(), L1lastwithL2)

Clearly, doing recursion on L2 is easier here because the 2nd one requires us to write another function insert_first. Of course, there is an exercise here on how to do that. So, 2nd approach is also viable.

Personal tools
Namespaces
Variants
Actions
Navigation
Toolbox
EECS @ UM
Tools