public class RecursionExamples
{
/* A string is a palindrome if:
1. Its length is 0 or 1
2. The first and last chars match, and the
inside is a palindrome
*/
public static boolean isPalindrome (String text)
{
System.out.println("Entering isPalindrome(\"" + text + "\")");
boolean result = false;
if (text.length() < 2) // explicit base case
{
result = true; //return true;
}
else
{
result = ( (text.charAt(0) == text.charAt(text.length() - 1)) &&
isPalindrome(text.substring(1, text.length() - 1)) );
}
System.out.println("Leaving isPalindrome(\"" + text + "\")");
return result;
}
// Recursively compute the nth Fibonacci number
public static int fibonacci (int n)
{
System.out.println("Entering fibonacci(" + n + ")...");
int result = -1;
if (n < 2) // base case: fib(0) and fib(1) are both 1
{
result = 1;
}
else
{
// Recursive case
result = fibonacci(n-1) + fibonacci(n-2);
}
System.out.println("Leaving fibonacci(" + n + ")...");
return result;
}
// Solve the Towers of Hanoi problem for n discs over three
// poles: source, destination, and temp
public static void hanoi (int n, String src, String dst, String tmp)
{
// Base case: n = 1 disc
if (n <= 1)
{
System.out.println("Move 1 disc from " + src + " to " + dst);
}
else
{
// Recursive case
hanoi(n-1, src, tmp, dst);
hanoi(1, src, dst, tmp);
hanoi(n-1, tmp, dst, src);
}
}
}