Recursion in Java

Recursion is used to reduce the size of a problem at each step.

• Easy to solve problem is known as base case
• Formula that reduces the size of problem is called general case
• Where as, a method that calls itself either directly or indirectly, is known as recursive method
• Any problem that can be solved using recursive calls can also be solved using a loop
• Recursive solution provides simpler, more elegant and more compact code

There are two key requirements to make sure that the recursion is successful:

• Every recursive call must simplify the computation in some way.
• There must be special cases to handle the simplest computations

Iteration Vs. Recursion

• If a recursive method is called with a base case, the method returns a result. If a method is called with a more complex problem, the method divides the problem into two or more conceptual pieces: a piece that the method knows how to do and a slightly smaller version of the original problem. Because this new problem looks like the original problem, the method launches a recursive call to work on the smaller problem.
• For recursion to terminate, each time the recursion method calls itself with a slightly simpler version of the original problem, the sequence of smaller and smaller problems must converge on the base case. When the method recognizes the base case, the result is returned to the previous method call and a sequence of returns ensures all the way up the line until the original call of the method eventually returns the final result.
• Both iteration and recursion are based on a control structure: Iteration uses a repetition structure; recursion uses a selection structure.
  Both iteration and recursion involve repetition: Iteration explicitly uses a repetition structure; recursion achieves repetition through repeated method calls.
• Iteration and recursion each involve a termination test: Iteration terminates when the loop-continuation condition fails; recursion terminates when a base case is recognized.
• Iteration and recursion can occur infinitely: An infinite loop occurs with iteration if the loop-continuation test never becomes false; infinite recursion occurs if the recursion step does not reduce the problem in a manner that converges on the base case.
• Recursion repeatedly invokes the mechanism, and consequently the overhead, of method calls. This can be expensive in both processor time and memory space.

Example – Print Welcome to Java World n times using recursive method

package coding.guru.com;

public class RecursionExamples {

	public static void print(int n) {
		if (n > 0) {
			System.out.println("Welcome to Java World");
			print(n - 1);
		}
	}

	public static void main(String[] args) {
		// call print method

		print(5);
	}
}

Step by step execution of above program

On first call from main method print(5 ), where n = 5

Print : “Welcome to Java World”

On 1st recursive call print (n-1) = print(5-1) = print(4)

Print : “Welcome to Java World”

On 2nd recursive call print (n-1) = print(4-1) = print(3)

Print : “Welcome to Java World”

On 3rd recursive call print (n-1) = print(3-1) = print(2)

Print : “Welcome to Java World”

On 4th recursive call print (n-1) = print(2-1) = print(1)

Print : “Welcome to Java World”

On 5th recursive call print (n-1) = print(1-1) = print(0)

Terminates the program because it don’t satisfy if else criteria, therefore no more recursive call

Computing factorial using recursive method

package coding.guru.com;

public class RecursionExamples {

	public static void print(int n) {
		if (n > 0) {
			System.out.println("Welcome to Java World");
			print(n - 1);
		}
	}

	/*
	 * Computing the factorial of a number using recursion
	 */
	public static int factorial(int n){
		if(n<=0)
			return 1;
		else
			return (n*factorial(n-1));
	}
	
	public static void main(String[] args) {
		// call print method

		//print(5);
		
		//Call factorial method and print result
		System.out.println(factorial(5));

	}

}

Step by step execution of above program

On first call from main method factorial(5 ), where n = 5

Returning : “1*1”

On 1st recursive call factorial (n-1) = factorial(5-1) = factorial(4)

Returning : “2*1”

On 2nd recursive call factorial(n-1) = factorial(4-1) = factorial(3)

Returning : “3*2”

On 3rd recursive call factorial(n-1) = factorial(3-1) = factorial(2)

Returning : “4*6”

On 4th recursive call factorial(n-1) = factorial(2-1) = factorial(1)

Returning : “5*24” which is factorial(5) = 5! = 120

On 5th recursive call factorial(n-1) = factorial(1-1) = factorial(0)

Watch video for more details :

Terminates the program because it don’t satisfy if else criteria, therefore no more recursive call

Note : Some of the text is taken from http://www2.hawaii.edu/~tp_200/lectureNotes/recursion.htm