How does structural recursion differ from generative recursion?

Question

The description of generative recursion in Wikipedia is clear to me, but I'm confused about the concept of structural recursion.

Can someone explain if a function calculating nth Fibonacci number and a function calculating factorial from 1 to N will be structural or generative?

Solution

The key difference between structural and generative recursion is where a recursive procedure gets the data that it works on and how it processes that data. Specifically, for structural recursion, a recursive call is made on a subset of the original input data. Whereas for generative recursion, a recursive call is made on data that was constructed/calculated from the original input data.

For example, if you wanted to count the number of elements in a linked list, you could do the following:

int NumberOfNodes(ListNode* node) {
    if (node == nullptr) return 0;
    return 1 + NumberOfNodes(node->next);
}

Here, the recursive call to NumberOfNodes is being made on node->next, which is a piece of the original input which already existed. In this case, the recursion works by breaking down the input into smaller pieces, then recursing on the smaller pieces.

Similarly, this code to search a BST for a value would be structural recursion, because the recursive calls are to subparts of the original input:

TreeNode* Find(TreeNode* root, DataType value) {
    if (root == nullptr) return nullptr;
    if (value < root->value) return Find(root->left, value);
    else return Find(root->right, value);

The term "structural recursion" comes from the fact that these structures (lists, BSTs, etc.) can be defined recursively:

• A list is either nothing, or a cell followed by a list.
• A binary tree is either nothing, or a node with two binary trees as children.

When doing structural recursion, you are "undoing" the operation from which these structures are built out of one another. For example, the NumberOfNodes function "undoes" the construction of taking a node and prepending it to an existing list. The Find operator "undoes" the operation of gluing a node to two other trees. Therefore, it's easy to see why these functions have to terminate - eventually, you "undo" all of the operations that went in to building up the object in the first place, and the recursion stops.

On the other hand, consider Quicksort, which does the following:

1. Pick a pivot.
2. Create three new lists: one of all elements less than the pivot, one of all elements greater than the pivot, and one of all elements equal to the pivot.
3. Recursively sort the first and second of these lists.
4. Concatenate the list of smaller, equal, and larger values.

Here, the recursive calls are being made on smaller arrays that weren't part of the original input - the lists had to be created from the data. (Typically, an implementation would reuse space for these lists, but those sublists weren't guaranteed to exist directly within the input).

This distinction is blurry when it comes to natural numbers. Usually, natural numbers are recursively defined as follows:

• 0 is a natural number.
• If n is a natural number, n + 1 is a natural number.
• Nothing else is a natural number.

Under this definition, the number n is a "part" of n + 1. Therefore, this recursive code to compute n! is structural recursion:

int Factorial(int n) {
    if (n == 0) return 1;
    return n * Factorial(n - 1);
}

This is structural recursion, because the argument n - 1 was a "part" of the original input n.

Similarly, by this definition, computing the nth Fibonacci number recursively counts as structural recursion:

int Fibonacci(int n) {
    if (n <= 1) return n;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

This is considered structural recursion because n - 1 is a part of n (formed by "undoing" the +1) and n - 2 is a part of n - 1 (again formed by "undoing" the +1).

On the other hand, this code to compute gcd would be considered generative recursion, rather than structural recursion:

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

The reasoning is that since a % b is "computed" from a and b, rather than formed by "undoing" some number of +1 operations, the data is generated.

The reason that generative recursion is different from structural recursion is that there's no guarantee that it terminates. For example, think about this function:

int BadTimes(int a, int b) {
    if (a == 0 && b == 0) return 0;
    return BadTimes(a * 2, b - 1);
}

This generative recursive function never terminates: a keeps getting bigger even though b keeps getting smaller.

Honestly, I've never heard of this distinction before and I teach courses in discrete math and programming. I wouldn't worry too much about it unless someone is requiring you to know the difference.

Hope this helps!

Comments

[Admin]

My two pennies: Fib is generative recursive using that definition because the data is "generated" as it goes along. Whereas, according to the article, structural recursion is about traversing an [existing] graph. The article goes on to state that an crucial distinction is that structural recursion can be proven to terminate through structural induction ..

[templatetypedef]

@pst- I think that Fibonacci actually is structural recursion. It's not so much about "generating" data as it as about how you come up with the arguments to the recursive calls.

[A. K.]

From the examples you gave and the ones in wikipedia, I get a notion that all the divide and conquer algorithms (if implemented recursively) will come under generative recursion.

[templatetypedef]

@AdityaKumar- Pretty much yes, but not necessarily; it depends on the structure in question. For example, finding the maximum value in a tree can be done with a divide-and-conquer approach, but is still structural recursion.

[A. K.]

Hmm... The binary search example in the generative recursion was one of the biggest contributors to my confusion.

[templatetypedef]

@AdityaKumar- I think that's related to how you define an array. I think their definition is "an array is either nothing or a value followed by an array." Under that definition, cutting an array in half isn't "undoing" the construction operation. Again - I honestly think this is a meaningless distinction; I've never encountered this before in many years of doing discrete math.

[Hibou57]

The key difference mentionned at the beginning, isn’it that of accumulative recursion?

[aspiringsoftwaredev]

You're a hero...

[tgbrooks]

The distinction matters in some formal proof systems. Structural recursion is the 'easy' kind and anything else requires proof of termination to be used. See exlean.org/well-founded-recursion or leanprover-community.github.io/extras/… for examples using Lean.