Linked lists with recursions

Topics To Cover

Recursive structure of a list
Printing a list recursively
Deleting a list recursively.
Recursive add2back

Recursive structure of a list

It turns out that a lot of linked list operations are very easily accomplished with recursion. The reason for this is that there is an essentially recursive way of looking at lists. Recall that "a list" in our program is really a pointer to the first node in a linked 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 a pointer of type Node*, and therefore it represents a list.
However, by the same reasoning, the next-field of the node containing 87 (shown in blue below) also represents a list.
- LIST->next is of type Node*.
- In particular, LIST->next represents the sublist containing 42, 53, and 4 — that is, everything but the first element of the list represented by LIST.

Important: Recursive structure of a list
A list (represented by LIST) consists of

The first value (represented by LIST->data)
The sublist (represented by LIST->next)

Printing a list

To write a recursive function to print out a linked list, we can start with the template below, and then fill in the two comment lines.

Base case
First we have to answer the question, "What should happen in the base case?" Another way of putting that is, "What should happen when we try to print an empty list?"

And the answer is, nothing! So we can just print a new line.

Recursive case
The second question is, "What do we do for each node in the list?"

That's easy too!

print the first value
print all the values in the sublist (recursion!)


void printlist(Node* list) 
{
  if (list == NULL) {
    // base case: list is empty 
  } 
  else 
  {
    // recursive case: list is not empty 

    // step 1: print the first value
    // step 2: Recursion: print the sublist 
  }
}

This gives us the following function:


void printlist(Node* list) {
  if (list == NULL)
  {
    cout << endl;
  } 
  else 
  {
    cout << list->data << " ";

    Node* sublist = list->next;
    printlist(sublist);
  }
}

Deleting a list recursively

One place recursion really "shines" with linked lists is in deleting a list. The logic goes like this:

If the list is empty, there's nothing to delete.
Otherwise, do:
1. Then delete the first (head) node.
2. Use recursion to delete the sublist first.


void deletelist(Node* list)
{
  // Base case: list is empty
  // There is nothing to do 
  if (list  == NULL) 
    return;  

  // Recurive case: list is not empty 

  // Identify the sublist 
  Node* sublist = L->next;

  // Delete the first node
  delete list;               

  // Delete the sublist (recursively)
  deletelist(sublist);    
}

Recursion vs. Loop

The purpose of learning recursion is not simply to make code shorter, but to learn how to write elegant and expressive functions.

Exploring multiple ways to solve a problem helps you develop a deeper understanding of both the problem itself and programming as a whole.

Sometimes recursion provides a cleaner or more intuitive solution for a given problem, while other times a loop feels more natural.
Because you are likely more familiar with loops, it may take practice—by writing many small recursive functions—to develop an instinct for when recursion is the better choice.

add2back(d, L)

We may want to add a node at the back of a list. For this, we can think of the following function:


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

As with add2front() the function returns the pointer to the head node of the updated list.
Note that adding to the back of list is actually the same as adding to the back of its sublist!
Moreover, if L is empty, you are creating a new list containing a node with value d.


Node* add2back(string d, Node* list)
{    
  if (list == NULL)        
  {
    // base case: list is empty
    //  list should become a list having a single node containing d. 
    list = new Node{d, NULL};
  }
  else
  {
    // recursive case:
    Node* sublist = list->next;

    //  Have the sublist to add d in the back
    //  add2back() returns an updated sublist (with d added).
    Node* upd_sublist = add2back(d, sublist);

    //  Link up 
    list->next = upd_sublist; 
  }

  // Important: return the pointer to the head node of the list
  return list;                       
}

Visualiztion

You can check out the visualization of the following code:


#include <iostream>
using namespace std;

struct Node
{
  int data;
  Node* next;
};

Node* add2back(int n, Node* list);

int main()
{
  Node* second = new Node{20, NULL};
  Node* L = new Node{10, second};

  // SEE THIS
  L = add2back(30, L);
  return 0;
}

Node* add2back(int d, Node* list)
{
  if( list == NULL )
  {
    list = new Node{d, NULL};
  }
  else
  {
    Node* sublist = list->next;
    Node* upd_sublist = add2back(d, sublist);
    list->next = upd_sublist;
  }

  return list;
}

Go to pythontutor.com.
Choose "C++" as the language to visualize.
Copy and paste the code.
Click the "Visualize Execution" button.
Step through the code!

Mandatory Practice Problems

length and max. Consider the following code. Define the functions recursively so that program works as shown below.


struct Node
{
  string data;
  Node* next;
};

Node* add2back(string s, Node* list);
void print(Node* list);
int length(Node* list);
string max(Node* list);
void deletelist(Node* list);

int main()
{
  string s;

  Node* L = NULL;
  while( cin >> s && s != ";")
    L = add2back(s, L);

  print(L);
  cout << "length=" << length(L) << endl;
  cout << "max=" << max(L) << endl;

  deletelist(L);
  return 0;
}

Sample run:

$ ./prac
hello world nice weather semester ending soon ;
hello world nice weather semester ending soon
length=7
max=world

Solution