Does the Composite design pattern implement recursive behavior?

Question

The Composite design pattern allows us to call an operation() on a 'composite' node in a tree structure, and this operation() will be called on all of the children, subchildren and so on.

When an element's operation() is invoked, it is it's responsibility to call operation() on all of it's children, and so on. Each child responsible to invoke the operation on it's own direct children.

I understand why this has a recursive nature. When we learn of this design, the word 'recursion' is inside our heads all the time.

But can this be considered 'recursive behavior' in the strict sense of the word?

I always thought that recursion simply means a process where 'a function calls itself'. ('function' or 'method' or 'procedure' etc).

However, in the Composite design pattern, no method calls itself. A method calls the identically-named method in the objects composed with it (serving as it's 'children') - but it never calls itself (aka void operation(){ this.operation(); } never happens).

So, does the Composite design pattern create recursive behavior? Or does it create behavior resembling the nature of recursion? Is my definition of recursion wrong because it's too strict? If so, how would you define recursion?

Answer 1

Composite creates Recursive Data Type which then needs recursive functions or operations to fully traverse. In a sense Composite creates tree-like structure.

Then yes, Composite has recursive behavior.

Answer 2

The composite pattern is recursive in two dimensions - it is a recursive data structure, and the operation method is likewise called recursively

See http://en.wikipedia.org/wiki/Recursion_(computer_science) for a detailed explanation and more.

Note: the method Operation() is defined by the class, and under the hood it just takes a reference to an instance as an argument, so the method is, in fact, calling itself.

Answer 3

To complement the other answers, I'll add a historical aspect.

In traditional CS definition, recursion means as you say, "a function calls itself." But object member methods and polymorphic functions were probably not well understood or even known at the time of that definition. Now let's take the Composite pattern:

operation() is (traditionally) recursive in the Composite pattern because it gives the illusion at a certain level of abstraction that it's a "function calling itself" (that illusion is key because it's a kind of information hiding).

But in reality (as you so well pointed out with your code example void operation(){ this.operation(); }), we know that composite's operation isn't the same function calling itself.

This is a great example of how computer science is a science of abstractions. Definitions that apply at one level might not apply precisely at others, but that doesn't mean they're suddenly wrong.

Recursive algorithms to solve problems don't need to have a function call itself, but often they do. There are strengths and weaknesses to the approach. You could use that recursive approach in a composite structure at the right level of abstraction to solve problems recursively. Base cases in recursion with Composite would be the Leaf classes. Recursive cases are obviously the Composite classes.

Answer 4

I rather like to think of the Composite element as the aggregator, rather than the recursively defined element.

The point is that contained elements do not have to behave the same way as the composite. They don't even have to expose the same feature. For example, composite element may sum up the results from the contained elements. Contained elements can simply return a fixed value.

The fact that composite allows us to imagine it as a tree-like structure doesn't mean that it is strictly a recursion.

Example from this article looks more like a recursion: Composite Design Pattern. But example from this article looks more like an aggregation: Working With Collections.