Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
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 at 19:40

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
    
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 at 19:11
    
@Prog Yeah, basically. I really recommend reading about trees. –  Euphoric Mar 23 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 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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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