Replace Recursion with Iteration

public void countDown(int n) {
	if(n == 0) return;

	System.out.println(n + "...");
	waitASecond();
	countDown(n-1);
}

				

public void countDown(int n) {
	while(n > 0) {
		System.out.println(n + "...");
		waitASecond ();
		n -= 1;
	}
				

Motivation

The old recruiting practice says, "Never hire a developer who computes the factorial using Recursion". Recursion is often used without considering alternatives before using it. Though it is true that recursive solution is often more elegant and easier to spot than the iterative solution, one should take care not to abuse it. Complex Recursion that is hard to understand should probably be considered a "bad smell" in the code and a good candidate to be replaced with Iteration (usually in combination with some other Refactorings). Moreover, iterative solutions are usually more efficient than recursive solutions as they don't incur the overhead of the multiple method calls.

We use Recursion when we have to perform a complex task that can be broken into the several subtasks. Recursion is implemented as a method that calls itself to solve subtasks. During the recursive call the values of the local fields of the method are placed on the method stack until the subtask performed by a recursive call is completed. Thus, whenever recursive method is called, local fields are put on the method stack and used again after the recursive call is completed. The general approach to Refactoring could probably be to implement the alternative Stack that "simulates" the method stack where the local fields could be placed (the java.util.Stack class is a good candidate for this job).

Sometimes a recursive solution doesn't preserve any local fields during the recursive call, which makes Refactoring much easier. This is the case with, so called, tail recursions. Tail recursions are recursions where the recursive call is the last line in the method. Tail recursions are generally considered a bad practice and should be replaced with Iteration. This technique is well known to the people who work on compiler implementations. A good compiler usually perfomes this Refactoring on the fly (this is the earliest known example that machines adopted some XP practices :)

Mechanics

• Determine the base case of the Recursion. Base case, when reached, causes Recursion to end. Every Recursion must have a defined base case. In addition, each recursive call must make a progress towards the base case (otherwise recursive calls would be performed infinitely). In our example the base case is n == 0.
• Implement a loop that will iterate until the base case is reached.
• Make a progress towards the base case. Send the new arguments to the top of the loop instead to the recursive method.

The mechanics of some complicated Refactorings other than tail recursion Refactorings (for example, those that would use "home made" Stack to store the local fields of the method) are waiting to be defined. In the meantime, if you find yourself dealing with the particularly nasty recursion, don't forget that Substitute Algorithm is a valid Refactoring and a secret weapon when it comes to situations like this.

Example

Sputnik launching countdown is a simple example of tail recursion:

public class CountDown {
	public void countDown(int n) {
		if(n == 0) return;

		System.out.println(n + "...");
		waitASecond();
		countDown(n-1);
	}

	public void waitASecond() {
		try {
			Thread.sleep(1000);
		}
		catch (InterruptedException ignore) {
		}
	}

	public static void main(String[] args) {
		CountDown c = new CountDown();
		c.countDown(10);
	}
}
				

After Refactoring:

public class CountDown {
	public void countDown(int n) {
		while(n > 0) {
			System.out.println(n + "...");
			waitASecond ();
			n -= 1;
		}

	}

	public void waitASecond() {
		try {
			Thread.sleep(1000);
		}
		catch (InterruptedException ignore) {
		}
	}

	public static void main(String[] args) {
		CountDown c = new CountDown();
		c.countDown(10);
	}
}