text: 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
  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.