Java Recursion: Problem Solving Techniques For Programming

Computer Science is a lot of pattern identification, and computer programs use these patterns to solve many problems at once. It is a case of “If you have hammer, everything looks like a nail” or “The best way to solve a problem is asking someone else to do it for you”. Let me explain.

Java is a freely available programming language, and a platform, supported on over a billion devices from desktop, to smart phones, embedded controller systems and even sensor microprocessors. Recursion is a basic, yet powerful technique usually taught as part of introductory programming in Java.

Algorithms and Techniques

Some of the computer science techniques, patterns if you will, of problem solving are recursion, dynamic programming, and greedy strategies. These are patterns of problem solving that are widely applicable to computer programs used in advanced computer-science algorithms, to those used in GPS systems, and Google Maps for picking your routes. Several scheduling algorithms that pick best flight routes and ticket prices, like in travel booking websites. Kayak and Priceline use these algorithms. If that all sounds enticing, check out the lessons at Java and introductory programming.

Simple Example

Factorial of a number, N, is defined to be the product of numbers from 1 to N; i.e. N! = 1*2*3* … N. Clearly a straightforward way to calculate factorial is using a for-loop where temporary initialized to 1, will have to start incrementing a counter upto N, and keep track of the product. At the end of the iterations the temporary carries the result of the factorial of N.

However yet another equivalent, and accurate, mathematical definition of factorial function is using the recursive notation; i.e. N! = (N-1)!*N

In other words it is a mathematical statement saying, if you want factorial of N, N!, and you know the factorial of (N-1), (N-1)!, then here is how you can calculate the factorial of N.

Clearly a way of writing this as a program in iterative and recursive ways would be, like the routines Demo.factorial(), and the class Factorial. Each of the programs provide a different approach to writing recursion in Java – one using classical static function, other using class member, inherited from a base class implementing a recursion strategy.

Code Listing

class Demo {
    public static void main(String [] args) {
        Rec r = new Rec(5);
        System.out.println("Iterative");
        r.start_iterative();
        System.out.println("Recursive");
        r.start_recursive();
        Factorial fr = new Factorial(5);
        System.out.println("Iterative");
        fr.start_iterative();
        System.out.println("Recursive");
        fr.start_recursive();
        System.out.printf(" 1! = %d, 2! = %d, 10! = %d \n",
                          Demo.factorial(1), Demo.factorial(2), Demo.factorial(10));
    }
    public static int factorial(int N) {
        if ( N == 1 )
            return 1;
        return Demo.factorial( N -1 )* N;
    }
}
class Rec{
	int stop;
	public Rec(int s){
		this.stop = s;
	}
	public Rec() {
		this.stop = 0;
	}
	public void start_iterative() {
		for( int i = 0; i < this.stop; i++) {
			System.out.println("Hello world "+Integer.toString(i));
		}
	}
	public void start_recursive(int limit) {
		if ( limit <= this.stop ) {
			System.out.println("Hello world "+Integer.toString(limit));
			this.start_recursive( limit + 1);
		}
	}
	public void start_recursive( ) {
		this.start_recursive( 0 );
	}
}
class Factorial extends Rec {
	int rec_temp;
	public Factorial(int s){
		this.stop = s;
	}
	public void start_iterative() {
		int val = 1;
		for( int i = 1; i <= this.stop; i++) {
			val = val*i;
		}
		System.out.printf("Iterative factorial for %d = %d \n",this.stop, val);
	}
	public void start_recursive(int val, int result) {
		if ( val == 1 ) {
			System.out.printf("Recursive factorial %d = %d \n",this.stop, result);
			return;
		} else {
			this.start_recursive( val - 1, result*(val) );
		}
	}
	public void start_recursive( ) {
		this.start_recursive( this.stop, 1 );
	}
}

Compiling the Program

Compiling and running this program in Eclipse or Oracle (Sun) Java compiler javac as in Makefile, from Linux platform, using commands

all:
       javac rec.java
       java Demo

where, $ javac rec.java , is the command to compile the code, and then run the program, $java Demo , would give us results like (only part of it is shown for brevity),

 Iterative
 Iterative factorial for 5 = 120
 Recursive
 Recursive factorial 5 = 120
 1! = 1, 2! = 2, 10! = 3628800

Example 2 : Shortest Paths and GPS Routing

Let’s say you have to write a program to identify the shortest path to a given destination, Z, from your current location, A; this problem might occur in a GPS system, maps applications etc. One way to tackle this problem is to store the distances from each city to every other city – something a AAA printed map of yesteryear would do. However, using computers, we can do much better.

Let’s assume your starting location, A, is only connected to 3 other cities B, C, and D – the cities at 1-hop distance from A, by dist_B, dist_C, dist_D miles respectively. Assuming C, and D have paths to Z, of lengths dist_C, and dist_D, we can detect the shortest path from A → Z by finding the shortest of paths from A to Z via B, or A to Z via C, i.e. (A → B + B → Z, A → C + C → Z ). This is clearly a recursive recipe to calculate the path from source to destination. This is the strategy behind algorithms like Djkstra graph search; learn more on Algorithms and data structures.

First you ask if any of your neighbors are able to find a way to destination. Do this recursively. If none of the neighbors are able to find a way to destination then you cannot find a path. However if two neighbors or more have paths to the destination, you pick the minimum length path from your current location to the intermediate (from which a path is already available to home).

Recursion and Iteration

You may also be familiar with consumer advertising on Internet, auto-completion in searches – these are data processing in the age of Big Data. Mostly such algorithms start out as small scale recursive programs, before they are changed from recursive programs to iterative ones. All recursive programs can be rewritten into iterative programs by maintaining your own stack.

Things to Watch Out For

1. Termination condition: If your termination condition is not set correctly you may run into the issue of infinite recursion – and your program may run out of stack space
2. Mutually recursive functions: Recursive functions that call each other, i.e. mutually recursive functions, are very powerful in computer programming. They are used in all sorts of things from parsers and compilers to design patterns like visitor
3. Resource usage of recursive functions: Computational cost in space and time of recursive functions can be significantly higher. While it is easy to write recursive functions they consume a lot of stack space, and you may have to choose an equivalent iterative algorithm sometimes.

Summary

Recursion is a programming technique where you can solve a problem by solving smaller versions of the same problem, up to a stopping condition, and then composing the solutions to achieve the solution to the, original, larger problem. If you think that sounds very mathematical, then you may be right! Learning to program in Java along with algorithms and data structures form pivotal elements in computer programming, helping you to achieve user functions with optimal resources.