Recursion Part 5: Structural and Generative Recursion

The following is a part of a series of articles I had written on recursion.

---

This part deals with two areas for which recursion is commonly applied. The first, called structural recursion, is used to traverse through different parts of a data structure, processing each part in some way. The second, called generative recursion, is used when we want to divide a problem into smaller subproblems, which are then solved.

All Parts:

Recursion Part 1: Introduction to recursion
Recursion Part 2: Tail recursion, Accumulators and Iteration
Recursion Part 3: Exercises in tail recursion
Recursion Part 4: Tree Recursion and Dynamic Programming
Recursion Part 5: Structural and Generative Recursion
Recursion Part 6: References and Further Information

---

Let us start of with structural recursion. Here is an example, an inorder traversal of a binary tree:

void inorder(node element)
{
    if (NULL == element) {
        return
    }
    inorder(element->left);
    process(element->data);
    inorder(element->right);
}

This is a classic case of structural recursion. Each recursive call processes a part of the binary tree. Put together, we process all the elements in the tree. Structural recursion is often used when dealing with self-referential data structures like lists, trees and graphs. Functions to deal with these structures are hard to implement with iteration¹, and even if we do manage to implement them with iteration, the resultant code is often very difficult to understand. Such code is best left as recursive.

In some cases, it is possible to modify the data structure itself so that common operations can be implemented iteratively. An example of this is the threaded tree data structure that modifies the classic binary tree to allow for iterative traversal.

In any case, except for exceptional cases, it is best to use recursive algorithms to implement structural recursion

Generative recursion is often used when we want to break up a problem into similar subproblems. The subproblems are solved and the results combined to get the final solution. Solving the subproblems in turn requires recursion to break the problem into smaller subproblems, and so on until we reach a trivial case. The recursive examples of factorial and fibonacci number calculations and the well known quicksort are examples of generative recursion.

Look at this fibonacci program again and convince yourself that it uses generative recursion:

int fibonacci(int n)
{
    if (0 == n) {
        return 0;
    } else if (1 == n) {
        return 1;
    } else {
        return fibonacci(n - 2) + fibonacci(n - 1);
    }
}

Generative recursion that operates on a known finite set (eg: fibonacci(n) operates on integers between 0 and n) are good candidates for a dynamic programming approach. Generative recursion that operates on large or unknown sets (eg: functions that work with real numbers often fall into this category) are usually not condusive to dynamic programming. Some cases of generative recursion may have good iterative solutions, but this has to be considered on a case by case basis. In most cases, it is best to just leave them recursive.

Of course, all the above only applies to tree recursion. Tail recursion, whether structural or generative can always be converted into iteration.

---

¹ The exception is linked lists. Linked lists usually result in tail recursion which can be converted to iteration.

---

Any questions? Comments? Please leave a comment using the comment form below.

This post is a part of the selected archive.