Node:Controlled recursion with data structures, Next:Recursion summary, Previous:Controlled recursion, Up:Recursion

Controlled recursion with data structures

Self-similar data structures are sometimes called recursive data structures. The simplest recursive data structure is the linked list. At every node in a linked list, there is data of a certain type and a link to the next node. The next simplest recursive data structure is the binary tree, which splits into two branches at every node. Recursive functions be useful for manipulating such recursive data structures.

The following code example makes use of recursion to print the value contained in the last node in a linked list.

#include <stdio.h>

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

struct list_node *last_node (struct list_node *node)
{
  if (node->next == NULL)
    return node;
  else
    return last_node (node->next);
}

/* To shorten example, not using argp */
int main ()
{
  struct list_node *root;
  struct list_node *current;
  struct list_node *old;
  struct list_node *last;

  /* Initialize list. */
  root = (struct list_node *) malloc (sizeof (struct list_node));
  root->data = 1;
  old = root;

  current = (struct list_node *) malloc (sizeof (struct list_node));
  current->data = 2;
  old->next = current;
  old = current;

  current = (struct list_node *) malloc (sizeof (struct list_node));
  current->data = 3;
  old->next = current;
  current->next = NULL;

  /* Print data in last node. */
  last = last_node (root);
  printf ("Data in last node is %d.\n", last->data);

  return 0;
}

This example program prints out the following line:

Data in last node is 3.

The last_node function, when passed a pointer to a node (such as the root), follows the linked list to its end from that point, and returns a pointer to that node. It does so through recursion. When it is passed a pointer to a node, it checks whether that node's next link is a null pointer. If the pointer is null, last_node has found the last node, and bottoms out, returning a pointer to the current node; otherwise, it calls itself with a pointer to the next node as a parameter.