# CP164 Lab 7 : Recursion (Cont'd)

###### 2019-12-29 08:12

Week of

1. Make a new version of the linked List `_linear_search` that is recursive rather than iterative. Name it `_linear_search_r` .

Test `List_linked.py`:

2. Add the following code to your `List_linked.py` List implementation:

```    def is_identical(self, target):
"""
---------------------------------------------------------
Determines whether two lists are identical.
(iterative version)
Use: b = source.is_identical(target)
-------------------------------------------------------
Parameters:
target - another list (List)
Returns:
identical - True if this list contains the same values as
target in the same order, otherwise False.
-------------------------------------------------------
"""
if self._count != target._count:
identical = False
else:
source_node = self._front
target_node = target._front

while source_node is not None and source_node._value == target_node._value:
source_node = source_node._next
target_node = target_node._next

identical = source_node is None
return identical
```

Implement and test a recursive version of this method named `is_identical_r` . Hint: it requires an auxiliary function.

Test `List_linked.py`:

3. Add the following code to your `List_linked.py` List implementation:

```    def split_alt(self):
"""
-------------------------------------------------------
Splits the source list into separate target lists with values
alternating into the targets. At finish source list is empty.
Order of source values is preserved.
(iterative algorithm)
Use: target1, target2 = source.split()
-------------------------------------------------------
Returns:
target1 - contains alternating values from source (List)
target2 - contains other alternating values from source (List)
-------------------------------------------------------
"""
target1 = List()
target2 = List()
left = True

while self._front is not None:

if left:
target1._move_front_to_rear(self)
else:
target2._move_front_to_rear(self)
left = not left
return target1, target2
```

Implement and test a recursive version of this method named `split_alt_r` . Hint: it requires an auxiliary function.

Test `List_linked.py`:

4. Add the following code to your `List_linked.py` List implementation:

```    def intersection(self, source1, source2):
"""
-------------------------------------------------------
Update the current list with values that appear in both
source1 and source2. Values do not repeat.
(iterative algorithm)
Use: target.intersection(source1, source2)
-------------------------------------------------------
Parameters:
source1 - a linked list (List)
source2 - a linked list (List)
Returns:
None
-------------------------------------------------------
"""
source1_node = source1._front

while source1_node is not None:
value = source1_node._value
_, current, _ = source2._linear_search(value)

if current is not None:
# Value exists in both source lists.
_, current, _ = self._linear_search(value)

if current is None:
# Value does not appear in target list.
self.append(value)

source1_node = source1_node._next
return
```

Implement and test a recursive version of this method named `intersection_r` . Hint: it requires an auxiliary function.

Test `List_linked.py`:

5. Add the following code to your `List_linked.py` List implementation:

```    def union(self, source1, source2):
"""
-------------------------------------------------------
Update the current list with all values that appear in
source1 and source2. Values do not repeat.
(iterative algorithm)
Use: target.union(source1, source2)
-------------------------------------------------------
Parameters:
source1 - an linked list (List)
source2 - an linked list (List)
Returns:
None
-------------------------------------------------------
"""
source1_node = source1._front

while source1_node is not None:
value = source1_node._value
_, current, _ = self._linear_search(value)

if current is None:
# Value does not exist in new list.
self.append(value)
source1_node = source1_node._next

source2_node = source2._front

while source2_node is not None:
value = source2_node._value
_, current, _ = self._linear_search(value)

if current is None:
# Value does not exist in current list.
self.append(value)

source2_node = source2_node._next
return
```

Implement and test a recursive version of this method named `union_r` . Hint: it requires a single auxiliary function.

Test `List_linked.py`:

6. Add the following code to your `List_linked.py` List implementation:

```    def reverse(self):
"""
-------------------------------------------------------
Reverses the order of the elements in list.
(iterative algorithm)
Use: source.reverse()
-------------------------------------------------------
Returns:
None
-------------------------------------------------------
"""
self._rear = self._front
previous = None
current = self._front

while current is not None:
temp = current._next
current._next = previous
previous = current
current = temp

self._front = previous
return
```

Implement and test a recursive version of this method named `reverse_r` . Hint: it requires a single auxiliary function.

Test `List_linked.py`: