Recursion Part 2

Finding the Sum of an Array

It's actually the case that any programming problem can be solved with recursion. There are no cases when you actually need to use loops — everything can be done with recursion instead. There are actually programming languages (such as Haskell) in which there are no loops statements at all.

In Java, it's commonplace to use loops most of the time, but there are some cases when recursion is the more natural option. We'll look today at using recursion to solve some problems we'd normally use loops for — just to get the hang of using recursion.

For instance, we can use recursion to sum a list of numbers with code like this:


public static int sum(List numbers) {
    if (numbers.size() == 0) {
        return 0;
    } else {
        return numbers.get(0) + sum(numbers.subList(1, numbers.size()));
    }
}

This works by first including a base case. If the array is size 0, the sum must be 0 (since there are no numbers at all). Remember that we always have to have the base case!

Next we "peel off" the first number of the list. Then we recursively sum up all of the numbers except the first one. This is done by using the subList method to get the sublist consisting of all number but the first.

Then we simply add the two together. The sum of an array is equal to the first element plus the sum of all the rest of the elements.

This is available in Sum.java.

Palindromes

A palindrome is a word that reads the same backwards as forwards. For example, "step on no pets" or "never odd or even" are palindromes.

Let's write a method to test if a string is a palindrome or not. We can base on on the following recursive idea:

"A phrase is a palindrome if the first and last letters are the same, and if the rest of the phrase is also a palindrome."

Here is this implemented with Java:


public static boolean isPalindrome(String str) {
    int size = str.length();

    if (size <= 1) {
        return true;
    }
    else if (str.charAt(0) != str.charAt(size - 1)) {
        return false;
    } else {
        return isPalindrome(str.substring(1, size - 1));
    }
}

This method starts by finding the size of the string and checking if it's 1 or less. If so, it must be a palindrome so it returns true. This serves as the base case.

Next, we check if the characters on either end don't match. If they don't, then it must not be a palindrome, so we return false.

Finally, we recurse. We do that by calling ourselves again on the string consisting of everything in the original string except the first and last characters.

This example is available as Palindrome.java.

Towers of Hanoi

There is a myth that there is a temple with three large towers. On the first tower are 64 golden rings where each one is smaller than the one under it. Monks at the temple are trying to move all of the rings from the first tower to the third tower.

There are three wooden poles representing the towers. The first has
10 rings on it, with the largest at the bottom and the smallest on top. — The Towers of Hanoi Game

However they must obey the rule that no ring can be placed on a ring that is smaller than it. To move the rings, they must use the third tower as a place holder to move the rings over while obeying the rule.

The myth states that when the monks are finished, and have moved all 64 rings to the third tower, the world will end.

We want to write a program that will figure out how to move all of the rings over, one by one.

Thinking of this recursively, to move any disc from the left tower to the right tower, we would first have to move all of the discs above it to the middle, then put the disc we want on the right, and then put all of the discs on the middle tower back on top at the right.

This is recursive because in defining how to move a disc, we say that we have to move other discs. This idea can be used to come up with a recursive algorithm like so:


To move a disc from left to right, using middle:
    First move all discs above us to the middle, using right.
    Then move this disc from the left to the right.
    Lastly move all discs from the middle to the right using left.

This program demonstrates this technique to solve the Towers of Hanoi: Towers.java.

This method calls itself twice each time through. This means the total number of steps needed doubles for each additional ring that we add. The number of moves is given in the following table:

Rings	Steps
1	1
2	3
3	7
4	15
5	31
6	63
7	127
8	255
9	511
10	1023
...	...
64	18446744073709551615

The number of steps is defined by the following formula:

$steps(rings) = 2^{rings} - 1$

This means that this algorithm is $O(2^n)$. This is called an exponential algorithm, and is completely impractical for large input sizes.

For doing a small number of discs, this doesn't take too terribly long. On my computer, given how long smaller numbers of discs take, it will take roughly 17 million years for the program to complete if we try all 64. Given that the monks are probably a lot slower than a computer, the world won't be ending any time soon :).