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

D. concat(L1, L2): returns a mylist that is a concatenation of L1 and L2.
 Revision as of 14:18, December 15, 2011 (view source)Aprakash (Talk | contribs) (Created page with "# return the concatenation of two lists. Best to solve recursively. Base case: L2 is empty. def concat(L1, L2): if (L2.isempty()): return L1 else: return...") Revision as of 17:45, December 15, 2011 (view source)Aprakash (Talk | contribs) Newer edit → Line 1: Line 1: − # return the concatenation of two lists. Best to solve recursively. Base case: L2 is empty. + 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. − def concat(L1, L2): + * Base case: If L2 is empty, then the answer is L1 + * Non-base case: L2 is non-empty. Breakdown L2 into L2.pop() and L2.last().  Assume concat is available to us for the recursive step. Think whether it is possible to construct the answer from L1, L2.pop(), and L2.last() using concat as well as other functions available to us. Strategy: Use concat to put together L1 and L2.pop(). But that is missing L2's last element. So, use append to add in L2.last(). + + Solution: + + def concat(L1, L2): if (L2.isempty()): if (L2.isempty()): return L1 return L1 else: else: return concat(L1, L2.pop()).append(L2.last()) 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

## Revision as of 17:45, 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.

• Base case: If L2 is empty, then the answer is L1
• Non-base case: L2 is non-empty. Breakdown L2 into L2.pop() and L2.last(). Assume concat is available to us for the recursive step. Think whether it is possible to construct the answer from L1, L2.pop(), and L2.last() using concat as well as other functions available to us. Strategy: Use concat to put together L1 and L2.pop(). But that is missing L2's last element. So, use append to add in L2.last().

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
```