Which is better to traverse a tree? Recursion Function or Loop Function?

Asked By 250 points N/A Posted on -
qa-featured

The application we are developing requires to find the levels of authority for a given user. The levels of authority follows a hierarchical tree like structure. An employee can have any number of supervisors. In order to traverse the tree structure, it is proposed to use recursion or a loop. What would be better?

SHARE
Best Answer by WhizBoy
Answered By 0 points N/A #91263

Which is better to traverse a tree? Recursion Function or Loop Function?

qa-featured

Recursion is normally used for traversing tree structures in programming. This "was" the recommended method for solving mathematical numbers such as getting the factorial of a number and the famous Fibonacci sequence. When a recursion is done, the method call goes to the STACK memory.

The call stack increases when the number of recursion increases. In event the stack limit is reached the program will crash with a Stack Overflow error. When you use a loop statement, it does not go to stack memory. Therefore a loop statement will be more "system" safe than using recursion.

Answered By 0 points N/A #91264

Which is better to traverse a tree? Recursion Function or Loop Function?

qa-featured

If the employee hierarchy is small, using recursion will be the easiest. Performance will be directly proportional to the "height" of the hierarchy. If the organization is a "flat" structure with less number of levels, use recursion. If the number of levels are high, as in the case of a "tall" organizational structure, recursion will be a performance hit. Using a loop is the best option.

Answered By 250 points N/A #91265

Which is better to traverse a tree? Recursion Function or Loop Function?

qa-featured

The number of employees are around 80 but the authority levels are in the form of a matrix structure. I have experienced stack-overflows with the test prototypes when we use recursion. Sometimes the whole machine gets stuck. Looks like the loop method looks viable. I have never used a loop to achieve a recursive function. Would you be able to post some sample code?

Answered By 0 points N/A #91266

Which is better to traverse a tree? Recursion Function or Loop Function?

qa-featured

The key thing in a recursive function is to have an "exit" condition for back tracking. The method calls itself is used as a track point until an exit condition is met. When you transform the same to a loop, you need to have a global variable to act as the exit point.

In your situation, the need will be to find an employees superiors. To prevent the program from scanning the same supervisor more than once, the "spent" supervisor need to be kept in a variable. As the loop progresses, the variable is checked if the current supervisor is checked. If not the program will loop to find the current persons supervisor.

Best Answer
Best Answer
Answered By 0 points N/A #91267

Which is better to traverse a tree? Recursion Function or Loop Function?

qa-featured

Actually in this case you will need to use a combined method of a loop AND a recursion. We minimize the recursion by ignoring duplicate employees. Following is a sample code for getting the sub-ordinates, given a username. you can reverse engineer it for your purpose.

Collection subOrdinateUsers = new ArrayList(0);  // global variable

private Set getSubordinates(String username) {
  //retreive data…and loop
 for (Iterator iter = userTemp.iterator(); iter.hasNext();) {
 
    if (!this.subOrdinateUsers.contains(element.getValue())) {
       subOrdinateUsers.add(element.getValue());
                //recursion
       subOrdinates.addAll(getSubordinates(element.getValue().toString()));
   }
 }
return subOrdinates;
}
 
Since the global variable is in the memory that is accessible to all the method calls in the stack, the recursive call count is reduced as duplicate names are skipped.
Answered By 250 points N/A #91268

Which is better to traverse a tree? Recursion Function or Loop Function?

qa-featured

The combined method works. It reduced the number in the call stack! Thank you WhizBoy for the sample code. I was able to reverse engineer it to find the supervisors for a given employee. Your code was a good guidance for me!

Answered By 0 points N/A #91269

Which is better to traverse a tree? Recursion Function or Loop Function?

qa-featured

Combination of recursion and a loop is the best for tree traversal where the structure is like a matrix. I agree with WhizBoy! Great post!

Login/Register to Answer

Related Questions