Basic idea of Recursion

Recursion

Recursion occurs when a method calls itself. Such a method is called recursive. A recursive method may be more concise than an equivalent non-recursive approach. However, for deep recursion, sometimes an iterative solution can consume less of a thread's finite stack space.

This topic includes examples of recursion in Java.

Basic idea of recursion

What is recursion:

In general, recursion is when a function invokes itself, either directly or indirectly. For example:

// This method calls itself "infinitely"
public void useless() {
    useless(); // method calls itself (directly)
}

Conditions for applying recursion to a problem:

There are two preconditions for using recursive functions to solving a specific problem:

  • There must be a base condition for the problem, which will be the endpoint for the recursion. When a recursive function reaches the base condition, it makes no further (deeper) recursive calls.
  • Each level of recursion should be attempting a smaller problem. The recursive function thus divides the problem into smaller and smaller parts. Assuming that the problem is finite, this will ensure that the recursion terminates

In Java there is a third precondition: it should not be necessary to recurse too deeply to solve the problem; see Deep recursion is problematic in Java

Example

The following function calculates factorials using recursion. Notice how the method factorial calls itself within the function. Each time it calls itself, it reduces the parameter n by 1. When n reaches 1 (the base condition) the function will recurse no deeper. 

public int factorial(int n) {
	if (n <= 1) { // the base condition
		return 1;
	} else {
		return n * factorial(n - 1);
	}
}

This is not a practical way of computing factorials in Java, since it does not take account of integer overflow, or call stack overflow (i.e. StackOverflowError exceptions) for large values of n.

Deep recursion is problematic in Java

Consider the following naive method for adding two positive numbers using recursion:

public static int add(int a, int b) {
	if (a == 0) {
		return b;
	} else {
		return add(a - 1, b + 1); // TAIL CALL
	}
}

This is algorithmically correct, but it has a major problem. If you call add with a large a, it will crash with a StackOverflowError, on any version of Java up to (at least) Java 9.

In a typical functional programming language (and many other languages) the compiler optimizes tail recursion. The compiler would notice that the call to add (at the tagged line) is a tail call, and would effectively rewrite the recursion as a loop. This transformation is called tail-call elimination.

However, current generation Java compilers do not perform tail call elimination. (This is not a simple oversight. There are substantial technical reasons for this; see below.) Instead, each recursive call of add causes a new frame to be allocated on the thread's stack. For example, if you call add(1000, 1), it will take 1000 recursive calls to arrive at the answer 1001.

The problem is that the size of Java thread stack is fixed when the thread is created. (This includes the "main" thread in a single-threaded program.) If too many stack frames are allocated the stack will overflow. The JVM will detect this and throw a StackOverflowError.

One approach to dealing with this is to simply use a bigger stack. There are JVM options that control the default size of a stack, and you can also specify the stack size as a Thread constructor parameter. Unfortunately, this only "puts off" the stack overflow. If you need to do a computation that requires an even larger stack, then the StackOverflowError comes back.

The real solution is to identify recursive algorithms where deep recursion is likely, and manually perform the tail-call optimization at the source code level. For example, our add method can be rewritten as follows: 

public static int add(int a, int b) {
    while (a != 0) {
        a = a - 1;
        b = b + 1;
    }
    return b;
}

(Obviously, there are better ways to add two integers. The above is simply to illustrate the effect of manual tail-call elimination.)

Why tail-call elimination is not implemented in Java (yet)

There are a number of reasons why adding tail call elimination to Java is not easy. For example:

  • Some code could rely on StackOverflowError to (for example) place a bound on the size of a computational problem.
  • Sandbox security managers often rely on analyzing the call stack when deciding whether to allow non-privileged code to perform a privileged action

Types of Recursion

Recursion can be categorized as either Head Recursion or Tail Recursion, depending on where the recursive method call is placed.

In head recursion, the recursive call, when it happens, comes before other processing in the function (think of it happening at the top, or head, of the function).

In tail recursion, it’s the opposite—the processing occurs before the recursive call. Choosing between the two recursive styles may seem arbitrary, but the choice can make all the difference

A function with a path with a single recursive call at the beginning of the path uses what is called head recursion. The factorial function of a previous exhibit uses head recursion. The first thing it does once it determines that recursion is needed is to call itself with the decremented parameter. A function with a single recursive call at the end of a path is using tail recursion.

public void tail(int n){
	if(n == 1) 
		return;
	else
		System.out.println(n);
 
	tail(n-1);
}
 
 
public void head(int n)
{ 
	if(n == 0)
		return;
	else 
		head(n-1);
 
	System.out.println(n);
}

Basic Programs

Learn All in Tamil © Designed & Developed By Tutor Joes | Privacy Policy | Terms & Conditions