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?

  • 1
    There's multiple types of recursion. Another that is undoubtedly recursion, but fails the naive "a function calls itself" test, would be mutual recursion
    – Izkata
    Mar 23, 2014 at 19:40

4 Answers 4


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.

  • Let me see if I understand: 1- Any data structure (could be an object in OOP) that contains another data structure of the same type - thus implementing the same methods - is considered a Recursive Data Type. For example, an ArrayList containing ArrayLists is a Recursive Data Type, and an object of class ContainerThing that contains objects of type ContainerThing is also a Recursive Data Type. 2- Any method in a Recursive Data Type that calls the identical method in one of the Recursive Data Type's contained objects - is considered recursive. Are both of these correct?
    – Aviv Cohn
    Mar 23, 2014 at 19:11
  • @Prog Yeah, basically. I really recommend reading about trees.
    – Euphoric
    Mar 23, 2014 at 19:18
  • Are there any more ways recursion can exist? Or is it only a function-calling-itself or function-calls-identical-function-in-contained-object?
    – Aviv Cohn
    Mar 23, 2014 at 19:19

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.


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:

UML for 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.


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.

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.