Java Reference
In-Depth Information
Can you always speed up a recursive solution by changing it into a loop? Frequently,
the iterative and recursive solution have essentially the same performance. For
example, here is an iterative solution for the palindrome test.
public boolean isPalindrome()
{
int start = 0;
int end = text.length() - 1;
while (start < end)
{
char first =
Character.toLowerCase(text.charAt(start));
char last =
Character.toLowerCase(text.charAt(end);
if (Character.isLetter(first) &&
Character.isLetter(last))
{
// Both are letters.
if (first == last)
{
start++;
end--;
}
else
return false;
}
if (!Character.isLetter(last))
end--;
if (!Character.isLetter(first))
start++;
}
return true;
}
This solution keeps two index variables:
start
and
end
. The first index starts at the
beginning of the string and is advanced whenever a letter has been matched or a
nonletter has been ignored. The second index starts at the end of the string and moves
toward the beginning. When the two index variables meet, the iteration stops.
Both the iteration and the recursion run at about the same speed. If a palindrome has n
characters, the iteration executes the loop between n/2 and n times, depending on how
many of the characters are letters, since one or both index variables are moved in each
