Comment lines: Looping versus recursion for improved application performance

No matter the purpose or scale of an application, performance is always a critical factor. Looping and recursion are comparable but different methods for computational coding. Developers might use one or the other method by default due to their familiarity with that method, but applying some analysis to determine the right method for the job could ultimately have a significant impact on application performance. This content is part of the IBM WebSphere Developer Technical Journal.

Brian S Paskin (bpaskin@us.ibm.com), Senior WebSphere Consultant, IBM China

Brain Paskin is a veteran of IBM for 18 years and has worked for IBM in Germany, Italy and the US. He is currently working for IBM Software Services for WebSphere helping customers with WebSphere MQ, WebSphere Application Server, DataPower implementation, performance, and other issues. Brian has helped write two IBM Redbooks and is certified on several IBM products.



17 July 2013

Also available in Chinese

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.

Figure 1. Summation test case
Figure 1. Summation test case

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.

Figure 2. Factorial test case
Figure 2. Factorial test case

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.

Resources

Comments

developerWorks: Sign in

Required fields are indicated with an asterisk (*).


Need an IBM ID?
Forgot your IBM ID?


Forgot your password?
Change your password

By clicking Submit, you agree to the developerWorks terms of use.

 


The first time you sign into developerWorks, a profile is created for you. Information in your profile (your name, country/region, and company name) is displayed to the public and will accompany any content you post, unless you opt to hide your company name. You may update your IBM account at any time.

All information submitted is secure.

Choose your display name



The first time you sign in to developerWorks, a profile is created for you, so you need to choose a display name. Your display name accompanies the content you post on developerWorks.

Please choose a display name between 3-31 characters. Your display name must be unique in the developerWorks community and should not be your email address for privacy reasons.

Required fields are indicated with an asterisk (*).

(Must be between 3 – 31 characters.)

By clicking Submit, you agree to the developerWorks terms of use.

 


All information submitted is secure.

Dig deeper into WebSphere on developerWorks


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=1
Zone=WebSphere
ArticleID=937526
ArticleTitle=Comment lines: Looping versus recursion for improved application performance
publish-date=07172013