Topics To Cover

• Recursive structure of a list
• Printing a list recursively
• Computing the length of a list recursively
• Deleting a list recursively.
• Adding an item in the back of a list.

Recursive structure of a list

Suppose LIST is a variable of type Node* in our program, and suppose that it points to the list 87, 42, 53, 4 as illustrated in the following picture:

• LIST is an pointer of type Node* and therefore we say that it represents a list.
• However, by that same argument the next-field of the node with data-value 87 (colored blue below) also represents a list.
  • Note that LIST->next is of type Node*.
  • In particular, LIST->next represents a list containing 42, 53, 4, i.e. everything but the first element of the list that LIST is.

Printing a list

void printlist(Node* L) 
{
  if (L == NULL) {
    // base case:
    //    depends on what you're doing
  } else {
    // recursive case:
    // step 1: Do something with L->data before the recursion

    // step 2: Recursion
    printlist(L->next);

    // step 3: Do something with L->data after the recursion
  }
}

void printlist(Node* L) {
  if (L == NULL) {
    // printing an empty list - nothing to do here!
  } else {
    cout << L->data << " ";
    printlist(L->next);
  }
}

Length()?

Deleting a list recursively

• If the list is empty, there's nothing to delete.
• Otherwise, do:
  1. Use recursion to delete the child list first.
  2. Then delete the head node.
  Note the first node should be the last thing you delete (otherwise the next pointer in the first node, which has already been deleted, will be used; it will crash your program).

void deletelist(Node* L)
{
  // Base case: if the list is empty, there is nothing to delete
  if (L == NULL) 
    return;  

  // Use recursion to delete all the second-to-last nodes
  deletelist(L->next);    
  delete L;               // Then delete the first node
}

Sometimes recursion seems "better" for the problem at hand, and sometimes a loop is a more natural solution. But remember that, since you're more used to writing loops now, you won't get a good feel for this until you've written many small recursive functions.

add2back(d, L)

Node* add2back(int d, Node* L);

Recursive add2back()

Node* add2back(int d, Node* L)
{    
  // base case: 
  //  L is an empty list 
  //  create a list having a single node with d and return it
  if (L == NULL)        
    return new Node{d, NULL};

  // recursive case:
  //  Tell the child list to add a node.
  //  add2back() will give the updated child list (with a new node added back).
  //  L->next points to the child list that add2back() gave. 
  L->next = add2back(d, L->next);


  // Important: 
  //  Recall that a list is represented as a pointer pointing to the head (i.e., first) node. 
  //  In this case, we have no change of the first node, and so return L
  return L;                       
}

About return new Node{d, NULL};

This single line of code is a cool way to create, initialize, and return a node. This means the following:

return new Node{d, NULL};

Node* T = new Node;
T->data = d;
T->next = NULL;
return T;

Iterative add2back()

• If the list is empty, as above, return a new list containing a node with valud d.
• Otherwise, go to the last node, and update its next to point to the newly created node.

Node* add2back(int d, Node* L)
{
  if (L == NULL)
  { 
    // If the list is empty
    return new Node{d, NULL};
  }
  else
  { 
    // If the list is not empty 
    // Start with finding the last node in the list 
    Node* last = L;
    while(last->next != NULL)
      last = last->next;

    // add2back(): Add a node after the last node
    last->next = new Node{d, NULL};

    // Important: 
    //  Recall that a list is represented as a pointer pointing to the head (i.e., first) node. 
    //  In this case, we have no change of the first node, and so return L
    return L;
  }
}

Mandatory Practice Problems

1. The length of a list:

   
   int length(Node* );
   

   Solution (drag your mouse):

   int length(Node* L)
   {
     // BASE CASE
     if (L == 0)
       return 0;
   
     // RECURSIVE CASE
     return 1 + length(L->next); 
   }
   

2. Check if the values in the list is in order.

   
   bool inorder(Node* );
   

   For example, if the list looks like

   10 20 30 40 50

   The function will return true. On the other hand, if the list looks like

   10 20 30 50 40

   The function will return false.

   Solution

Other Practice Problems

1. Find the maximum value in a list of string's.

   
   string max(Node* );
   

   Solution (drag your mouse):

   string max(Node* L)
   {
     // base case: empty list or 1 node 
     if( L == NULL )
       return "";
     else if (L->next == NULL)
       return L->data;
   
     // recursive case
     string maxC =  max(L->next);  // maximum from the child list
     if( L->data > maxC )
       return L->data;
     else
       return maxC;
   }