CODEWITHSUNDEEP
javarecursion
u123
u123

Reputation: 16329

Writing a recursive method in java

I am trying to write a recursive method that searches through a list of IData objects and returns a specific implementation. The list contains objects that implements the interface IData.

There are two implementations of this interface:

1) DataImpl

2) DataContainerImpl

The DataContainerImpl has a:

 List<IData> children;

so it can hold nested DataContainerImpl elements or just plain DataImpl's. Here is what I do:

  public static DataContainerImpl findDataContainerWithName(Collection<IData> elements, String name) {
    for (IData  element : elements) {
      if (element instanceof DataContainerImpl) {
        DataContainerImpl container = (DataContainerImpl) element;
        if (container.getName().equals(name)) {
          return container ;
        }

       container = findDataContainerWithName(container.getChildren(), name);
       if (container != null) {
         return container ;
       }
      }
    }
    return null;
  }

Upvotes: 1

Views: 1538

Answers (4)

DNA
DNA

Reputation: 42617

Apart from the problems already mentioned in answers, you are making a recursive call for each element in the list, passing in all the other elements.

So for a list of length N, you will recurse N-deep (needlessly), popping one element off the list each level of recursion. But all of these elements can be handled at the same level.

You are artificially increasing the recursion depth, hence your StackOverflowError problem

Upvotes: 1

Kal
Kal

Reputation: 24910

Not exactly sure what you are doing here, but calling "findContainerByName()" recursively without a "return" in front of it wont do you any good.

The recursive call will return , but then the call will drop to the bottom and return null.

For example, if your list contained just 1 DataContainerImpl whose name did not match the name you called the method with, but it contains inside it a list with again just 1 DataImpl, you will still get null back. Is this what you want?

Upvotes: 5

P&#233;ter T&#246;r&#246;k
P&#233;ter T&#246;r&#246;k

Reputation: 116306

I think the root cause of your problem is that you keep recursively searching through the same elements in the list. I.e. here 

    // Call with remaining list...
    Collection<IData> copyAll = EcoreUtil.copyAll(elements);
    copyAll.remove(count);
    findDataContainerWithName(copyAll, name);

you call with the original list minus the current element, not only with the elements after the current element. So the recursive calls will inspect the same elements over and over again, needlessly. Especially so as you are looping over the list each time, which would be needless with a pure recursive approach.

So if you absolutely want to make this search recursive, you should only inspect the first element, then remove it from the list and call recursively with the remaining list. Or if you prefer looping over the list, you don't need any recursion in the common case (when the element is not a DataContainerImpl). That would be the Java way of doing things btw, as Java - unlike functional languages - has limited support for recursion.

Upvotes: 1

Neil
Neil

Reputation: 55432

Stick to your original loop to handle the list, and only recurse when you find a DataContainerImpl.

  public static DataContainerImpl findDataContainerWithName(Collection<IData> elements, String name) {
    for (IData element : elements) {
      if (element instanceof DataContainerImpl) {
        DataContainerImpl container = (DataContainerImpl) element;
        if (container.getName().equals(name)) {
          return container;
        }
        container = findDataContainerWithName(container.getChildren(), name);
        if (container) {
          return container;
        }
      }
    }
    return null;
  }

Upvotes: 4

Related Questions