1
$\begingroup$

I have a question about generally accepted terminology (and whether it exists at all).

Some recursive algorithms on hierarchical data structures (trees) have the property that they are expressed as a function which does a single recursive function call on each of its children, and that this call takes no parameters other than the child node.

Example in Python:

def sum_of_values(node):
    result = node.value 
    for child in node.children:
        result += sum_of_values(child)
    return result

Other algorithms do not have this property, and fundamentally cannot have this property.

Consider, for example, a mechanism for pretty-printing an AST, which has the property that we want the first child of any node to be displayed on a single line, but all the other nodes on their own line.

Also sketched in Python, leaving out many details (e.g. indentation):

def pretty_print(node, single_line_mode=False):
    if single_line_mode:
        return "(" + " ".join([pretty_print(child, True) for child in node.children]) + ")" 

    result = "(" 
    if len(node.children) >= 1:
        result += pretty_print(node.children[0], True)

    for child in node.children[1:]:
        result += "\n" + pretty_print(child, False)

    result += ")" 
    return result

The key point of the above is: The recursive call contains more information than simply the fact that some work must be done recursively. This information flows from the structure higher up in the tree (in this case: whether the some node in the path of presently printed node to the root of the tree is the first child of its parent).

If we were to rewrite the above by replacing the boolean parameter with 2 functions, our algorithm is no longer expressed in terms of a single recursive function call for each on each of the children.

So we can see a distinction: algorithms in which we can do calculations for constituent parts of a composite data structure independently from the data structure of which they are a part, and those for which this is not possible.

Is there an accepted terminology for this distinction?

Edit to add:

In the context of parallel computing, recursive definitions of the first kind (no additional parameters in the recursive call) are automatically Embarrassingly Parallel

$\endgroup$
2
$\begingroup$

This sounds to me like a Catamorphism, specifically, a Tree Fold. If you're familiar with the foldr list function of functional programming (I believe Python has this too), this is also a catamorphism.

In general, the categories functions are divided into like this are called recursion schemes. The classic introduction to them is Bananas, Lenses, Envelopes and Barbed Wire. If you're familiar with Haskell, the modern translation guide might help.

Some more information is provided in the Origami Programming paper.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.