The elegant recursive solution to a problem is most of the times invaluable. Although the iterative solution of that problem is likely to have a better space and time complexity, it is often preferred to use the recursive version for clarity and simplicity. It is remarkable how easily a problem can be solved by use of a recursive manner. In this article we will try to record a collection of useful recursive functions:

The following recursive function calculates the function N! using the standard recursive definition. It returns the correct value when called with N non-negative and small enough so that N! can be represented as an integer type ‘int’.

int
factorial (int N) {
  if (N == 0) return 1;

  return N * factorial (N-1);
}

The following recursive function was developed as an algorithm by Euclid 2000 years ago. It is considered one of the oldest known algorithms and can be used for finding the greatest common divisor of two numbers.

int
gcd (int m, int n) {
  if (n == 0) return m;

  return gcd (n, m % n);
}

The following recursive function can be used to count the nodes of a singly linked list.

int
count (link x) {
  if (x == 0) return 0;

  return 1 + count (x->next);
}

The following recursive function can traverse all nodes in a singly linked list and process each node separately through a processing function.

void
traverse (link h, void visit (link)) {
  if (h == 0) return;

  visit (h);

  traverse (h->next, visit);
}

The following recursive function works like the above but with the only difference being that it visits the nodes of a singly linked list in reverse order.

void
traverseR (link h, void visit (link)) {
  if (h == 0) return;

  traverseR (h->next, visit);

  visit (h);
}

The following recursive function removes from a singly linked list all nodes that have a given value.

void
remove (link &x, Item v) {
  while (x != 0 && x->item == v) {
    link t = x;
    x = x->next;
    delete t;
  }

  if (x != 0)
    remove (x->next, v);
}

The following function divides an array a[l], …, a[r] to a[l], …, a[m] and a[m+1], …, a[r]. Then, it finds the maximum element in each of the two parts (recursively), and returns the larger of the two as a maximum element in the overall array. If the array size is even, both parts have the same size. However, if it is odd, the sizes of the two parts of the array differ by 1. Also, it is worth mentioning that for the data type ‘Item’, we must have overloaded the comparison operator ‘>’ to run the following function.

Item
max (Item a[], int l, int r) {
  if (l == r) return a[l];

  int m = (l+r) / 2; 

  Item u = max (a, l, m);
  Item v = max (a, m+1, r);

  if (u > v)
    return u;
  else
    return v;
}

The following function provides a recursive solution to the Towers of Hanoi.

void
hanoi (int N, int d) {
 if (N == 0) return;

 hanoi (N-1, -d);
 shift (N, d);   
 hanoi (N-1, -d);
}

The following “divide and conquer” recursive function can be used to design marks on a ruler. More specifically, to design the marks on a ruler, we first design the appropriate signs in the left half, then the longest mark in the middle, and then the appropriate signs in the right half.

void
rule (int l, int r, int h) {
  int m = (l+r) / 2;

  if (h > 0) {
    rule (l, m, h-1);
    mark (m, h); // painting function.
    rule (m, r, h-1);
  }
}

The following recursive function can be used to generate a sequence of Fibonacci numbers. However, it is not such a good solution because whenever it is called, it starts to count from the beginning throughout the sequence. In particular, it has not got a history or memory to improve the response time of the function in the future.

int
F (int i) {
  if (i < 1) return 0;
  if (i == 1) return 1;

  return F (i-1) + F (i-2);
}

The following recursive function can be used to generate a sequence of Fibonacci numbers. This implementation, however, is a better solution than the previous one because it retains memory (Dynamic Programming) from which it can derive the results directly in future calls without having to recalculate a sequence from the beginning.

int
F (int i) {
  static int knownF[maxN];

  if (knownF[i] != 0) return knownF[i];

  int t = i;

  if (i < 0) return 0;

  if (i > 1) t = F (i-1) + F (i-2);

  return knownF[i] = t;
}

The following recursive function accepts a link to a binary tree and process each node of the tree. As it is now, the code implements the prefix tree traversal. If you move the call of function ‘visit’ between the recursive calls we will have infix traversal of the tree. But, if you move the call of function ‘visit’ after the recursive calls, we will have postfix traversal of the tree.

void
traverse (link h, void visit (link)) {
  if (h == 0) return;

  visit (h);
  traverse (h->l, visit);
  traverse (h->r, visit);
}

The following recursive function can be used to count the nodes of a binary tree.

int
count (link h) {
  if (h == 0) return 0;

  return count (h->l) + count (h->r) + 1;
}

The following recursive function can be used to calculate the height of a binary tree.

int
height (link h) {
  if (h == 0) return -1;

  int u = height (h->l), v = height (h->r);

  if (u > v)
    return u+1;
  else
    return v+1;
}

The following recursive function is applied onto a graph and it actually implements the method of depth-first search. To visit all the nodes connected to node k of a graph, we note that node as the node that we have visited and then visit (recursively) all the nodes we have not visited and are included in the adjacency list of k.

void
traverse (int k, void visit (int)) {
  visit (k); visited[k] = 1;

  for (link t = adj[k]; t != 0; t = t->next)
    if (!visited[t->v]) traverse (t->v, visit);
}