Recursion

Recursion is a kind of divide-and-conquer programming technique that can be used to simplify a more complicated to advanced problem into simpler subproblems.

For example, if we were to find out whether a string is a palindrome or not, we could iterate through the whole string using a loop, but we can also check it using recursion.

First we notice the base case: if a string contains no letters or one single letter, that string is a palindrome.

If we don't have a string with length 0 or 1, we notice that this string is a palindrome as long as the two letters on either end of the string are the same and that the substring made by taking off the two letters at the ends is a palindrome. Here is a simple demonstration without code to find out if racecar is a palindrome:

Is "racecar" a palindrome? The two letters on the ends: "racecar" are the same, so it should be a palindrome if "aceca" is a palindrome.

Is "aceca" a palindrome? The two letters on the ends: "aceca" are the same, so it should be a palindrome if "cec" is a palindrome.

Is "cec" a palindrome? The two letters on the ends: "cec" are the same, so it should be a palindrome if "e" is a palindrome.

Is "e" a palindrome? Yes, because it only has one letter. Therefore, it must be a palindrome.

As you could see from the demonstration, we repeatedly asked if the next substring is a palindrome until we reached a simple base case. Here is a code implementation of the above demonstration

public boolean isPalindrome(String input) {

int len = input.length();

// Check for base case

if (len <= 1) {

return true; // Always palindromes

}

if (input.charAt(0) != input.charAt(len - 1)) {

return false; // cannot be a palindrome

}

else {

// Check to see if the smaller substring is

// a palindrome through a recursive call

return isPalindrome(input.substring(0, len));

}

}

// Code written by Jimmy Liu