Comment lines

# Looping versus recursion for improved application performance

## This content is part # of # in the series: Comment lines

Stay tuned for additional content in this series.

## This content is part of the series:Comment lines

Stay tuned for additional content in this series.

## Coding for performance

Programmers are always looking for the most productive way to improve performance within an application. While most programmers know the concepts of looping and recursion, many only implement one or the other without thought of how much of a performance improvement can be made by choosing the correct method. In fact, a small change can dramatically affect performance.

## Recursion

Recursion in computer science is a term meaning a method that calls itself. That is a simple definition for a term that is sometimes hard to understand because humans do not usually think in this manner. To confuse matters even more, there are several different types of recursion. The two types of recursion that are most often used are:

• Head recursion is when the recursive call is initiated near the beginning of the method. It is one of the first items to be processed, and since it is calling itself it relies on the result of the previous operation that had been placed on the call stack. Since it uses the call stack to process, there is a possibility of a stack overflow if the call stack is not large enough.
• Tail recursion occurs when the recursive call is at the end and is the last line of code to be processed. This method does not use the call stack no matter the depth of the recursive call.

Recursion does occur naturally in mathematics, so it might be easier to express recursion with the recursive call. For example, factorials are recursive. The expression 5! (5 factorial) can be evaluated in the following manner:

```5! 5 * 4! 5 * 4 * 3! 5 * 4 * 3 * 2! 5 * 4 * 3 * 2 * 1! 5 * 4 * 3 * 2 * 1```

Listing 1 shows a head recursive example of evaluating 5!.

##### Listing 1
```public long getFactorial(long currNum) {
if (currNum == 1)
return 1;

return currNum * getFactorial(currNum - 1);
}```

Each recursive call needs to be completed and placed on the call stack before calculating the factorial. Here is how Java™ would interpret each time through the getFactorial method, with each line representing an item on the call stack:

```5 * getFactorial(4) 5 * (4 * getFactorial(3)) 5 * (4 * (3 * getFactorial(2))) 5 * (4 * (3 * (2 * getFactorial(1)))) 5 * (4 * (3 * (2 * 1))) 120```

Listing 2 shows a tail recursive example of evaluating 5!.

##### Listing 2
```public long getFactorial(long currNum, long sum) {
if (currNum == 0)
return sum;

return getFactorial(currNum - 1, sum *= currNum);
}```

Each recursive call is calculated and does not rely on the call stack to save information that is necessary to calculate the factorial. Instead, it passes the result of the previous call.

##### Listing 3
```getFactorial(5,0)
getFactorial(4,5)
getFactorial(3,20)
getFactorial(2,60)
getFactorial(1,120)
getFactorial(0,120)
120```

## Looping

Most programmers are usually very familiar with loops, and programming languages feature several different types of loops. In the Java programming language there are for, do and while loops. A loop is the repeat execution of a number of statements. Loops do not add to the call stack no matter the number of times the loop is executed. One important difference between loops and recursive functions is that loops use an iterator to traverse the loop, while recursive functions must compare the results to know when to exit. Another important difference is that filters and other selectors can be used within a loop. An example of this would be using a foreach type of for loop.

## Which is better?

There is no easy answer to that question. In many instances, loops offer better performance than recursion, as method calls are more costly than executing regular statements. In the case of head recursion, the call stack is increased and must be traversed to get the final answer. However, this is not always the case and it depends on the type of work that is being done.

## Test cases

The test cases below were run using the 64 bit IBM Java Runtime Environment (JRE) 7.0.4.0 (with -Xms256m -Xmx256m -Dcom.ibm.tools.attach.enable=no). The settings start the JRE with a fixed 256 megabytes of heap to prevent spending time trying to expand and contract the heap. Disabling the attach API prevents the JRE from enabling agent applications (usually used for monitoring), which kept performance normalized during each test. When the call stack was increased, -Xss3m -Xssi3m was used to start the stack and maintain the stack at 3 megabytes.

### Summation test

In the case of summation of numbers, looping exhibits much better performance, and tail recursion is faster than head recursion. However, when the Java call stack is increased to 3 megabytes, head recursion is just as fast as tail recursion, but still not as fast as looping.

### Factorial test

This is a unique case that highlights how results can be affected by the statements being executed. Using the primitive data type int, all results were much faster using a loop. Using int limits the results to a 32 bit signed number. For larger factorials, a BigInteger can be used, but costs more to construct. The results using a BigInteger show that using head recursion with tail recursion is faster over a pure tail recursion or looping solution.

## When to use recursion

Recursion is a very powerful tool for programmers. It can be used to solve problems that would be more efficiently expressed in recursion and can take advantage of the call stack. Programs that require some type of sorting tend to be the problems that can be solved with recursion with improved results over loops.

The problem called the Towers of Hanoi — in which you are given three pegs and different size discs setup like a tower on the first peg, and you try to transfer the tower from the first peg to another peg without having a larger disc placed on top of a smaller disc — is good match for recursion. Using recursion the solution can be achieved in 2n - 1 moves, where n is the number of discs.

For example, given four discs and trying to move from peg A to peg C, using peg B temporarily, can be done in 15 moves using the recursive function below. This can be visualized using this applet. The function is called (2n * 2) – 1 or 31 times. The reason why the number of function calls does not equal the number of moves is that the call stack needs to be setup to be able the process the moves. This example uses head recursion. (Listing 4)

##### Listing 4
```private  static void solveTower(int num, int fromPeg, int toPeg,
int tempPeg) {
if (num > 0) {
// move a disc from the fromPeg to the tempPeg
solveTower(num - 1, fromPeg, tempPeg, toPeg);

System.out.println("Disc moved from " + fromPeg + " to " + toPeg);

// move disc from the tempPeg to the toPeg
solveTower(num - 1, tempPeg, toPeg, fromPeg);
}
}```

The output given 4 discs is shown in Listing 5.

##### Listing 5
```1. Disc moved from 1 to 2
2. Disc moved from 1 to 3
3. Disc moved from 2 to 3
4. Disc moved from 1 to 2
5. Disc moved from 3 to 1
6. Disc moved from 3 to 2
7. Disc moved from 1 to 2
8. Disc moved from 1 to 3
9. Disc moved from 2 to 3
10. Disc moved from 2 to 1
11. Disc moved from 3 to 1
12. Disc moved from 2 to 3
13. Disc moved from 1 to 2
14. Disc moved from 1 to 3
15. Disc moved from 2 to 3```

The Towers of Hanoi is a well understood problem that can be solved with recursion. Not all problems are obvious and require time to analyze the problem and solution. The Towers of Hanoi problem can also be solved using loops; however, the solution requires several different loops and iterators. The solution would take longer to run and requires more code to effectively do the same processing.

Below is iterative way to solve the Towers of Hanoi. The sample uses bitwise operations, which tend to be faster than mathematic operations. This was adapted from this C program.

##### Listing 6
```int  numMoves = (1 << numDiscs) - 1;
int [] pegs = { 1, 2, 3, 1, 3, 2 };
int  count = 0;

for  (int currMove=1; currMove <= numMoves; currMove++) {
int disc = 0;
while ( (currMove >> disc & 1) == 0 ) {
disc++;
}
int level=(numDiscs - disc) & 1;
int fromPeg =(currMove >> ++disc) % 3;
fromPeg = pegs[fromPeg + (level * 3)];
int toPeg =(fromPeg + level) % 3 + 1 ;
System.out.println (++count + ". Disc moved from " + fromPeg  + " to " + toPeg) ;
}```

## Conclusion

Although programmers might be more familiar with looping, recursion should also be considered, especially if performance can be gained or the call stack can be utilized to help solve the problem. It is not always easy to predict which method will produce better performance, thus performance testing the methods is necessary. If head recursion is going to be used, the call stack size must also be considered.