Definition

A recursive definition of a list:

• The empty list [] is a list
• If x is a value and r is a list, then we can construct a new list lst whose first element is x and whose other elements are the elements of r

Visualisation:

[1, 2, 3, 4] ==
([1] +
    ([2] +
        ([3] +
            ([4] + [])))

Python implementation

class RecursiveList:
    """A recursive implementation of the List ADT.

    Representation Invariants:
        - (self._first is None) == (self._rest is None)
    """
    # Private Instance Attributes:
    #   - _first: The first item in this list, or None if this list is empty.
    #   - _rest: A list containing the items in this list that come after the first one,
    #            or None if this list is empty.
    _first: Optional[Any]
    _rest: Optional[RecursiveList]

    def __init__(self, first: Optional[Any], rest: Optional[RecursiveList]) -> None:
        """Initialize a new recursive list."""
        self._first = first
        self._rest = rest

Optional is used because there doesn't necessarily have to be a _first element (empty list)

Operations

List Sum

Recursive definition: $$ \text{sum(lst)} = \begin{cases} 0, & \text{lst is empty} \\ \text{(first of lst)} + \text{sum of lst}, & \text{lst is non-empty} \end{cases} $$

Python implementation:

class RecursiveList:
    def sum(self) -> int:
        """Return the sum of the elements in this list.

        Preconditions:
            - every element in this list is an int
        """
        if self._first is None:  # Base case: this list is empty
            return 0
        else:                    # Recursive case: this list is non-empty
            return self._first + self._rest.sum()