In the following examples we shall use the following type definition to enable us to work on unsorted linked lists of integers:

TYPE
  (* The type of items stored in the list. *)
  ItemType = INTEGER;
  (* Type definitions for (Unordered) Lists *)
  ListPtr = REF ListRec;
  ListRec =
    RECORD
      next : ListPtr;
      value : ItemType;
    END;

Many problems that involve lists require us to write procedures that are recursive. Such procedures often have a very common structure:

IF the list is not empty THEN
  Do something to the item at the head of this list;
  Apply this procedure to the rest (tail) of the list;
END;

Because this structure is so common, we will make use of three procedures from our list module that will help us enormously, ListHead gives the value of the first item in the list, ListTail gives the remainder of the list with the first item removed, and ListIsNotEmpty returns TRUE if the list is not empty (or the alternatively ListIsEmpty, which returns TRUE if the list is empty). Using these procedures, many typical recursive procedures on lists will look something like this:

PROCEDURE ListProc(list : ListPtr) =
BEGIN
  IF ListIsNotEmpty(list) THEN
    Do something to ListHead(list);
    (* Apply this procedure to the rest of the list. *)
    ListProc(ListTail(list));
  END;
END ListProc;

Consider the following specification:

Write a procedure to say whether a particular value occurs in a list.

What are this procedure's inputs and outputs? It will take a value and a list as input, and return an output of TRUE or FALSE. So its header looks like this:

PROCEDURE IsInList(n : INTEGER; list : ListPtr) : BOOLEAN

Can we apply the ideas presented above in solving this problem? We should consider what it means if the list is empty, what it means if the value is at the head of the list and what it means if it is in the tail of the list. If the list is empty then the value is not in the list (FALSE). If the value is at the head of the list then it is in the list (TRUE). In order to find out if it is in the tail of the list, we just apply IsInList recursively. Here is a solution:

PROCEDURE IsInList(n : INTEGER; list : ListPtr) : BOOLEAN =
VAR found : BOOLEAN;
BEGIN
  IF ListIsNotEmpty(list) THEN
    IF n = ListHead(list) THEN
      found := TRUE;
    ELSE
      found := IsInList(n,ListTail(list));
    END;
  ELSE
    found := FALSE;
  END;
  RETURN found;
END IsInList;

How does this differ from our outline procedure? The biggest difference is that we don't automatically call the procedure recursively on the tail. If we find the value at the head of the list then there is no need to look any further. Both of these styles of processing a list recursively are common in problem solving, and you should get used to asking whether you need to do something to every element in the list or whether you can stop before reaching the end.

Consider the following specification:

Write a procedure to count how many times a value occurs in a list.

Follow the same sort of method that we have outlined above. Does every element of the list need to be considered? Try to reuse as much as possible of what you have seen so far in solving this problem.

Suppose that the specification told you that the list was sorted in ascending order of values (i.e. it is a sequence with possible duplicates). What differences would this make to your solution?