Recursion

What is Recursion

In general, recursion is the process of repeating items in a self-similar way. In programming, recursion is that a method calls itself to accomplish its purpose.

Recursion appears in many areas.

A recursive definition (or inductive definition) is defining an object in terms of itself. For example, an ancestor is

  • a parent, or
  • the parent of an ancestor.

Note that in the body of this definition, we use the term ancestor which is not completely defined yet.

In Mathematics and Computer Science, many concepts are defined recursively. A class of objects has recursive behavior if they can be defined by:

  • A simple base case, and
  • A set of rules reducing all other cases toward the base case.

For example, the factorial function of a positive integer n, denoted by n!, is defined as:

  • Base case:  1! =1
  • Recursive rules: for n > 1, n! = n * (n-1)!

This computation can be implemented with the following method:

public static long factorial(int n)
{
    if (n <= 1)
        return 1;
    return n * factorial(n - 1);
}

The method factorial() calls itself by passing in a smaller parameter. This process can illustrated below:

factorial(5)
    factorial(4)
        factorial(3)
            factorial(2)
                factorial(1)
                return 1
            return 2*1 = 2
        return 3*2 = 6
    return 4*6 = 24
return 5*24 = 120

A recursive computation can be transformed to a loop (iteration). For example, the factorial function can be computed as below, since n! = n * (n-1) * … *1.

public static long factorialWithLoop(int n)
{
    long f = 1;
    for (int i = 2; i <= n; i++)
        f *= i;
    return f;
}

Using Recursion

A palindrome is a word, number or phrase that may be read the same way in either direction. For example:

  • civic, radar, level
  • Never odd or even (ignoring upper/lower cases and spaces)
  • 121, 12321

The following method uses recursion to check whether a string is a palindrome.

public static boolean isPalindrome(String s)
{
    if (s.length() <= 1)
        return true;
    if (s.charAt(0) == s.charAt(s.length() - 1))
    {
        String substr = s.substring(1, s.length() - 1);
        return isPalindrome(substr);
    }
    return false;
}

Here we use two methods of the java.lang.String class:

  • public char charAt(int index) Returns the char value at the specified index.
  • public String substring(int beginIndex, int endIndex) Returns a substring beginning at beginIndex and ending at endIndex – 1.

Related document: http://docs.oracle.com/javase/7/docs/api/java/lang/String.html

Tower of Hanoi is a puzzle consisting of three pegs and a number of disks of different sizes. The puzzle starts with the disks stacked on one peg in order of size, the smallest at the top; the objective is to move all of the disks to another peg, obeying the following rules:

  • Only one disk may be moved at a time.
  • No disk may be placed on top of a smaller disk.
  • All disks must be on some peg except the one in transition.

Below is a recursive strategy to move n disks from the start peg to the destination peg:

  • Move the topmost n – 1 disks from the start peg to the extra peg
  • Move the largest disk from the start peg to the destination peg
  • Move the n – 1 disks from the extra peg to the destination peg

The base case is when there is only one peg and we can move it directly.

We label the start peg as 1, the extra peg as 2, and the destination peg as 3. The strategy above can be implemented using the following method.

public static void moveTower(int n, int start, int dest, int extra)
{
    if (n <= 1)         System.out.println(start + " --> " + dest);
    else
    {
        moveTower(n - 1, start, extra, dest);
        System.out.println (start + " --> " + dest);
        moveTower(n - 1, extra, dest, start);
    }
}

The print out by the statement gives actions we need to take to move disks. For example, “1 –> 3” means moving the top disk at peg 1 to peg 3.

The following method call solves the problem if the number of disks is totalDisks:

moveTower(totalDisks, 1, 3, 2);

References

Recursion
Tower of Hanoi
http://introcs.cs.princeton.edu/java/23recursion/

Comments

comments