Common Algorithms
Recursion Examples
Many practical problems involve repeated structure: arrays, strings, mathematical recurrence, and divide-and-conquer search. These examples show common recursive patterns with small, traceable inputs.
Sum of Array
Process one element, then recurse on the rest of the array.
ArraySum.java
import java.util.Arrays;
public class ArraySum {
public static int sum(int[] arr, int index) {
if (index >= arr.length) {
return 0;
}
return arr[index] + sum(arr, index + 1);
}
public static int sum(int[] arr) {
return sum(arr, 0);
}
public static int sumByLength(int[] arr, int n) {
if (n <= 0) {
return 0;
}
return arr[n - 1] + sumByLength(arr, n - 1);
}
public static void main(String[] args) {
int[] numbers = {1, 2, 3, 4, 5};
System.out.println("Array: " + Arrays.toString(numbers));
System.out.println("Sum (index approach): " + sum(numbers));
System.out.println("Sum (length approach): " + sumByLength(numbers, numbers.length));
int[] values = {10, 20, 30, 40};
System.out.println("\nArray: " + Arrays.toString(values));
System.out.println("Sum: " + sum(values));
}
}
Reverse String
String recursion removes one character at a time until the base case.
StringReverse.java
public class StringReverse {
public static String reverse(String str) {
if (str.length() <= 1) {
return str;
}
return str.charAt(str.length() - 1) + reverse(str.substring(0, str.length() - 1));
}
public static String reverseAlt(String str) {
if (str.length() <= 1) {
return str;
}
return reverseAlt(str.substring(1)) + str.charAt(0);
}
public static String reverseTrace(String str, int depth) {
String indent = " ".repeat(depth);
System.out.println(indent + "reverse(\"" + str + "\")");
if (str.length() <= 1) {
System.out.println(indent + " → \"" + str + "\"");
return str;
}
char last = str.charAt(str.length() - 1);
String rest = str.substring(0, str.length() - 1);
String result = last + reverseTrace(rest, depth + 1);
System.out.println(indent + " → \"" + result + "\"");
return result;
}
public static void main(String[] args) {
String[] words = {"hello", "recursion", "Java"};
for (String word : words) {
System.out.println(word + " → " + reverse(word));
}
System.out.println("\nAlternative approach:");
System.out.println("world → " + reverseAlt("world"));
System.out.println("\nWith trace:");
reverseTrace("abc", 0);
}
}
Power Function
Power.java
public class Power {
public static int power(int base, int exp) {
if (exp == 0) {
return 1;
}
return base * power(base, exp - 1);
}
public static int powerOptimized(int base, int exp) {
if (exp == 0) {
return 1;
}
if (exp % 2 == 0) {
int half = powerOptimized(base, exp / 2);
return half * half;
}
return base * powerOptimized(base, exp - 1);
}
private static int callCount = 0;
public static int powerCounted(int base, int exp) {
callCount++;
if (exp == 0) return 1;
return base * powerCounted(base, exp - 1);
}
public static int powerOptimizedCounted(int base, int exp) {
callCount++;
if (exp == 0) return 1;
if (exp % 2 == 0) {
int half = powerOptimizedCounted(base, exp / 2);
return half * half;
}
return base * powerOptimizedCounted(base, exp - 1);
}
public static void main(String[] args) {
int base = ;
int exponent = ;
System.out.println(base + "^" + exponent + " = " + power(base, exponent));
System.out.println("\nOptimized:");
System.out.println(base + "^" + exponent + " = " + powerOptimized(base, exponent));
callCount = 0;
int r1 = powerCounted(base, exponent);
int calls1 = callCount;
callCount = 0;
int r2 = powerOptimizedCounted(base, exponent);
int calls2 = callCount;
System.out.println("\nCalls for " + base + "^" + exponent + ":");
System.out.println(" Simple: " + calls1 + " calls");
System.out.println(" Optimized: " + calls2 + " calls");
}
}
public class Power {
public static int power(int base, int exp) {
if (exp == 0) {
return 1;
}
return base * power(base, exp - 1);
}
public static int powerOptimized(int base, int exp) {
if (exp == 0) {
return 1;
}
if (exp % 2 == 0) {
int half = powerOptimized(base, exp / 2);
return half * half;
}
return base * powerOptimized(base, exp - 1);
}
private static int callCount = 0;
public static int powerCounted(int base, int exp) {
callCount++;
if (exp == 0) return 1;
return base * powerCounted(base, exp - 1);
}
public static int powerOptimizedCounted(int base, int exp) {
callCount++;
if (exp == 0) return 1;
if (exp % 2 == 0) {
int half = powerOptimizedCounted(base, exp / 2);
return half * half;
}
return base * powerOptimizedCounted(base, exp - 1);
}
public static void main(String[] args) {
int base = ;
int exponent = ;
System.out.println(base + "^" + exponent + " = " + power(base, exponent));
System.out.println("\nOptimized:");
System.out.println(base + "^" + exponent + " = " + powerOptimized(base, exponent));
callCount = 0;
int r1 = powerCounted(base, exponent);
int calls1 = callCount;
callCount = 0;
int r2 = powerOptimizedCounted(base, exponent);
int calls2 = callCount;
System.out.println("\nCalls for " + base + "^" + exponent + ":");
System.out.println(" Simple: " + calls1 + " calls");
System.out.println(" Optimized: " + calls2 + " calls");
}
}
public class Power {
public static int power(int base, int exp) {
if (exp == 0) {
return 1;
}
return base * power(base, exp - 1);
}
public static int powerOptimized(int base, int exp) {
if (exp == 0) {
return 1;
}
if (exp % 2 == 0) {
int half = powerOptimized(base, exp / 2);
return half * half;
}
return base * powerOptimized(base, exp - 1);
}
private static int callCount = 0;
public static int powerCounted(int base, int exp) {
callCount++;
if (exp == 0) return 1;
return base * powerCounted(base, exp - 1);
}
public static int powerOptimizedCounted(int base, int exp) {
callCount++;
if (exp == 0) return 1;
if (exp % 2 == 0) {
int half = powerOptimizedCounted(base, exp / 2);
return half * half;
}
return base * powerOptimizedCounted(base, exp - 1);
}
public static void main(String[] args) {
int base = ;
int exponent = ;
System.out.println(base + "^" + exponent + " = " + power(base, exponent));
System.out.println("\nOptimized:");
System.out.println(base + "^" + exponent + " = " + powerOptimized(base, exponent));
callCount = 0;
int r1 = powerCounted(base, exponent);
int calls1 = callCount;
callCount = 0;
int r2 = powerOptimizedCounted(base, exponent);
int calls2 = callCount;
System.out.println("\nCalls for " + base + "^" + exponent + ":");
System.out.println(" Simple: " + calls1 + " calls");
System.out.println(" Optimized: " + calls2 + " calls");
}
}
public class Power {
public static int power(int base, int exp) {
if (exp == 0) {
return 1;
}
return base * power(base, exp - 1);
}
public static int powerOptimized(int base, int exp) {
if (exp == 0) {
return 1;
}
if (exp % 2 == 0) {
int half = powerOptimized(base, exp / 2);
return half * half;
}
return base * powerOptimized(base, exp - 1);
}
private static int callCount = 0;
public static int powerCounted(int base, int exp) {
callCount++;
if (exp == 0) return 1;
return base * powerCounted(base, exp - 1);
}
public static int powerOptimizedCounted(int base, int exp) {
callCount++;
if (exp == 0) return 1;
if (exp % 2 == 0) {
int half = powerOptimizedCounted(base, exp / 2);
return half * half;
}
return base * powerOptimizedCounted(base, exp - 1);
}
public static void main(String[] args) {
int base = ;
int exponent = ;
System.out.println(base + "^" + exponent + " = " + power(base, exponent));
System.out.println("\nOptimized:");
System.out.println(base + "^" + exponent + " = " + powerOptimized(base, exponent));
callCount = 0;
int r1 = powerCounted(base, exponent);
int calls1 = callCount;
callCount = 0;
int r2 = powerOptimizedCounted(base, exponent);
int calls2 = callCount;
System.out.println("\nCalls for " + base + "^" + exponent + ":");
System.out.println(" Simple: " + calls1 + " calls");
System.out.println(" Optimized: " + calls2 + " calls");
}
}
Efficient Exponentiation
Computing x^n by dividing the exponent reduces recursive work from O(n) toward O(log n).
Count Occurrences
Counting combines the current match with the recursive result for the rest.
Count.java
import java.util.Arrays;
public class Count {
public static int count(int[] arr, int index, int target) {
if (index >= arr.length) {
return 0;
}
int currentCount = (arr[index] == target) ? 1 : 0;
return currentCount + count(arr, index + 1, target);
}
public static int count(int[] arr, int target) {
return count(arr, 0, target);
}
public static int countChar(String str, char target) {
if (str.isEmpty()) {
return 0;
}
int currentCount = (str.charAt(0) == target) ? 1 : 0;
return currentCount + countChar(str.substring(1), target);
}
public static int countDigits(int n) {
if (n < 10) {
return 1;
}
return 1 + countDigits(n / 10);
}
public static void main(String[] args) {
int[] numbers = {1, 2, 3, 2, 4, 2, 5};
System.out.println("Array: " + Arrays.toString(numbers));
System.out.println("Count of 2: " + count(numbers, 2));
System.out.println("Count of 5: " + count(numbers, 5));
System.out.println("Count of 9: " + count(numbers, 9));
String text = "recursion";
System.out.println("\nString: " + text);
System.out.println("Count 'r': " + countChar(text, 'r'));
System.out.println("Count 'i': " + countChar(text, 'i'));
System.out.println("\nDigits in 12345: " + countDigits(12345));
System.out.println("Digits in 987: " + countDigits(987));
}
}
Recursive Binary Search
Binary search is a divide-and-conquer recursion over a sorted array.
BinarySearch.java
import java.util.Arrays;
public class BinarySearch {
public static int binarySearch(int[] arr, int left, int right, int target) {
if (left > right) {
return -1;
}
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] > target) {
return binarySearch(arr, left, mid - 1, target);
} else {
return binarySearch(arr, mid + 1, right, target);
}
}
public static int binarySearch(int[] arr, int target) {
return binarySearch(arr, 0, arr.length - 1, target);
}
public static int binarySearchTrace(int[] arr, int left, int right, int target, int depth) {
String indent = " ".repeat(depth);
if (left > right) {
System.out.println(indent + "Not found");
return -1;
}
int mid = left + (right - left) / 2;
System.out.println(indent + "Searching [" + left + ".." + right +
"], mid=" + mid + " (value=" + arr[mid] + ")");
if (arr[mid] == target) {
System.out.println(indent + "Found at index " + mid);
return mid;
}
if (arr[mid] > target) {
System.out.println(indent + "Go left");
return binarySearchTrace(arr, left, mid - 1, target, depth + 1);
} else {
System.out.println(indent + "Go right");
return binarySearchTrace(arr, mid + 1, right, target, depth + 1);
}
}
public static void main(String[] args) {
int[] numbers = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int target = ;
System.out.println("Array: " + Arrays.toString(numbers));
System.out.println("Search 7: index " + binarySearch(numbers, 7));
System.out.println("Search 15: index " + binarySearch(numbers, 15));
System.out.println("Search 8: index " + binarySearch(numbers, 8));
System.out.println("\nSearch " + target + " with trace:");
binarySearchTrace(numbers, 0, numbers.length - 1, target, 0);
}
}
import java.util.Arrays;
public class BinarySearch {
public static int binarySearch(int[] arr, int left, int right, int target) {
if (left > right) {
return -1;
}
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] > target) {
return binarySearch(arr, left, mid - 1, target);
} else {
return binarySearch(arr, mid + 1, right, target);
}
}
public static int binarySearch(int[] arr, int target) {
return binarySearch(arr, 0, arr.length - 1, target);
}
public static int binarySearchTrace(int[] arr, int left, int right, int target, int depth) {
String indent = " ".repeat(depth);
if (left > right) {
System.out.println(indent + "Not found");
return -1;
}
int mid = left + (right - left) / 2;
System.out.println(indent + "Searching [" + left + ".." + right +
"], mid=" + mid + " (value=" + arr[mid] + ")");
if (arr[mid] == target) {
System.out.println(indent + "Found at index " + mid);
return mid;
}
if (arr[mid] > target) {
System.out.println(indent + "Go left");
return binarySearchTrace(arr, left, mid - 1, target, depth + 1);
} else {
System.out.println(indent + "Go right");
return binarySearchTrace(arr, mid + 1, right, target, depth + 1);
}
}
public static void main(String[] args) {
int[] numbers = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int target = ;
System.out.println("Array: " + Arrays.toString(numbers));
System.out.println("Search 7: index " + binarySearch(numbers, 7));
System.out.println("Search 15: index " + binarySearch(numbers, 15));
System.out.println("Search 8: index " + binarySearch(numbers, 8));
System.out.println("\nSearch " + target + " with trace:");
binarySearchTrace(numbers, 0, numbers.length - 1, target, 0);
}
}
import java.util.Arrays;
public class BinarySearch {
public static int binarySearch(int[] arr, int left, int right, int target) {
if (left > right) {
return -1;
}
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] > target) {
return binarySearch(arr, left, mid - 1, target);
} else {
return binarySearch(arr, mid + 1, right, target);
}
}
public static int binarySearch(int[] arr, int target) {
return binarySearch(arr, 0, arr.length - 1, target);
}
public static int binarySearchTrace(int[] arr, int left, int right, int target, int depth) {
String indent = " ".repeat(depth);
if (left > right) {
System.out.println(indent + "Not found");
return -1;
}
int mid = left + (right - left) / 2;
System.out.println(indent + "Searching [" + left + ".." + right +
"], mid=" + mid + " (value=" + arr[mid] + ")");
if (arr[mid] == target) {
System.out.println(indent + "Found at index " + mid);
return mid;
}
if (arr[mid] > target) {
System.out.println(indent + "Go left");
return binarySearchTrace(arr, left, mid - 1, target, depth + 1);
} else {
System.out.println(indent + "Go right");
return binarySearchTrace(arr, mid + 1, right, target, depth + 1);
}
}
public static void main(String[] args) {
int[] numbers = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int target = ;
System.out.println("Array: " + Arrays.toString(numbers));
System.out.println("Search 7: index " + binarySearch(numbers, 7));
System.out.println("Search 15: index " + binarySearch(numbers, 15));
System.out.println("Search 8: index " + binarySearch(numbers, 8));
System.out.println("\nSearch " + target + " with trace:");
binarySearchTrace(numbers, 0, numbers.length - 1, target, 0);
}
}
GCD
Gcd.java
public class Gcd {
public static int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
public static int gcdTrace(int a, int b) {
System.out.println("gcd(" + a + ", " + b + ")");
if (b == 0) {
System.out.println(" → " + a);
return a;
}
return gcdTrace(b, a % b);
}
public static int lcm(int a, int b) {
return (a * b) / gcd(a, b);
}
public static int gcdIterative(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
public static void main(String[] args) {
System.out.println("GCD(48, 18) = " + gcd(48, 18));
System.out.println("GCD(100, 35) = " + gcd(100, 35));
System.out.println("GCD(17, 13) = " + gcd(17, 13));
System.out.println("\nGCD(48, 18) with trace:");
gcdTrace(48, 18);
System.out.println("\nLCM(12, 18) = " + lcm(12, 18));
System.out.println("LCM(7, 5) = " + lcm(7, 5));
System.out.println("\nIterative GCD(48, 18) = " + gcdIterative(48, 18));
}
}
Euclidean Algorithm
An efficient method to find the greatest common divisor: GCD(a, b) = GCD(b, a mod b), with base case GCD(a, 0) = a.
Exercise: Practical.java
Implement a recursive method to check if a string is a palindrome