Question

Write a recursive definition (not the code) for contains on a linked list of Node, starting at a given node, in the style from lecture. Then, implement boolean contains(Node node, int e) using recursion - no explicit loop constructs (for, while) allowed!

Answer 1

A recursive definition of contains on a linked list is that a list contains an element if the current node's value is equal to the element or if the rest of the list contains the element. To implement this definition, write a recursive function that checks if the node's value is equal to the element, and if not, calls itself with the next node until the element is found or the end of the list is reached.

Step-by-step explanation:

A linked list is a data structure where each node contains a value and a pointer to the next node. To define a recursive version of contains on a linked list, we can say that a list contains an element if the current node's value is equal to the element or if the rest of the list contains the element. We can express this as:

contains(node, e) = node.value == e || contains(node.next, e)

To implement this definition, we can write a recursive function contains that takes a node and an element as arguments, and checks if the node's value is equal to the element. If it is, we return true. If not, we call contains again with the next node and the same element until we reach the end of the list or find the element. If we reach the end of the list without finding the element, we return false.