Asked By
AnthonyW
250 points
N/A
Posted on - 05/09/2011
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?
Answered By
MathGirl
0 points
N/A
#91263
Which is better to traverse a tree? Recursion Function or Loop Function?
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
WhizBoy
0 points
N/A
#91264
Which is better to traverse a tree? Recursion Function or Loop Function?
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
AnthonyW
250 points
N/A
#91265
Which is better to traverse a tree? Recursion Function or Loop Function?
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
MathGirl
0 points
N/A
#91266
Which is better to traverse a tree? Recursion Function or Loop Function?
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.
Answered By
WhizBoy
0 points
N/A
#91267
Which is better to traverse a tree? Recursion Function or Loop Function?
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
AnthonyW
250 points
N/A
#91268
Which is better to traverse a tree? Recursion Function or Loop Function?
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
MathGirl
0 points
N/A
#91269
Which is better to traverse a tree? Recursion Function or Loop Function?
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!
