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.
