CP164 Lab 7 : Recursion (Cont'd)

Week of

See: The Five Rules of Recursion

  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: