WikiGalaxy
Common Recursion Problems
Understanding Recursion Problems:
Recursion is a powerful tool for solving problems that can be broken down into smaller, similar sub-problems. It is particularly useful in scenarios such as traversing data structures, solving puzzles, and performing repeated calculations.
When to Use Recursion:
Recursion should be used when a problem can naturally be divided into similar sub-problems, when the depth of recursion is manageable, and when an iterative solution would be complex or less intuitive.
Example 1: Factorial Calculation
Concept:
The factorial of a non-negative integer n is the product of all positive integers less than or equal to n. It is a classic example of a recursive problem.
public class Factorial {
public static void main(String[] args) {
System.out.println(factorial(5));
}
public static int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
}
Explanation:
This recursive function calculates the factorial of 5 by multiplying 5 by the factorial of 4, and so on, until it reaches the base case.
Console Output:
120
Example 2: Fibonacci Sequence
Concept:
The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones. It is a common example of a recursive problem.
public class Fibonacci {
public static void main(String[] args) {
System.out.println(fibonacci(5));
}
public static int fibonacci(int n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
Explanation:
This recursive function calculates the 5th Fibonacci number by summing the results of the 4th and 3rd Fibonacci numbers.
Console Output:
5
Example 3: Tower of Hanoi
Concept:
The Tower of Hanoi is a mathematical puzzle that consists of three rods and a number of disks of different sizes. The objective is to move the entire stack to another rod following specific rules.
public class TowerOfHanoi {
public static void main(String[] args) {
solveHanoi(3, 'A', 'C', 'B');
}
public static void solveHanoi(int n, char from, char to, char aux) {
if (n == 0) return;
solveHanoi(n - 1, from, aux, to);
System.out.println("Move disk " + n + " from " + from + " to " + to);
solveHanoi(n - 1, aux, to, from);
}
}
Explanation:
This recursive function solves the Tower of Hanoi puzzle for 3 disks, moving them from rod A to rod C using rod B as auxiliary.
Console Output:
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
Example 4: Binary Search
Concept:
Binary search is a divide-and-conquer algorithm used to find the position of a target value within a sorted array. It works by repeatedly dividing the search interval in half.
public class BinarySearch {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
System.out.println(binarySearch(arr, 0, arr.length - 1, 4));
}
public static int binarySearch(int[] arr, int left, int right, int target) {
if (right >= left) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] > target) return binarySearch(arr, left, mid - 1, target);
return binarySearch(arr, mid + 1, right, target);
}
return -1;
}
}
Explanation:
This recursive function performs a binary search on a sorted array to find the index of the target value 4.
Console Output:
3
Example 5: Permutations
Concept:
Generating permutations of a string involves rearranging its characters into all possible orders. Recursion is an effective way to explore all permutations.
public class Permutations {
public static void main(String[] args) {
permute("ABC", 0, 2);
}
public static void permute(String str, int l, int r) {
if (l == r) System.out.println(str);
else {
for (int i = l; i <= r; i++) {
str = swap(str, l, i);
permute(str, l + 1, r);
str = swap(str, l, i); // backtrack
}
}
}
public static String swap(String str, int i, int j) {
char[] charArray = str.toCharArray();
char temp = charArray[i];
charArray[i] = charArray[j];
charArray[j] = temp;
return String.valueOf(charArray);
}
}
Explanation:
This recursive function generates all permutations of the string "ABC" by swapping characters and recursively permuting the rest.
Console Output:
ABC
ACB
BAC
BCA
CBA
CAB
Example 6: String Reversal
Concept:
Reversing a string using recursion involves breaking the string into smaller parts and reversing each part recursively.
public class StringReversal {
public static void main(String[] args) {
System.out.println(reverse("hello"));
}
public static String reverse(String str) {
if (str.isEmpty()) return str;
return reverse(str.substring(1)) + str.charAt(0);
}
}
Explanation:
This recursive function reverses the string "hello" by recursively reversing the substring and appending the first character at the end.
Console Output:
olleh
Example 7: Palindrome Check
Concept:
A palindrome is a word, phrase, or sequence that reads the same backward as forward. Checking for palindromes can be done recursively by comparing characters from the ends towards the center.
public class PalindromeCheck {
public static void main(String[] args) {
System.out.println(isPalindrome("madam"));
}
public static boolean isPalindrome(String str) {
if (str.length() <= 1) return true;
if (str.charAt(0) != str.charAt(str.length() - 1)) return false;
return isPalindrome(str.substring(1, str.length() - 1));
}
}
Explanation:
This recursive function checks if the string "madam" is a palindrome by comparing characters from the ends towards the center.
Console Output:
true
Example 8: Sum of Digits
Concept:
Calculating the sum of digits of a number using recursion involves breaking down the number into its individual digits and summing them.
public class SumOfDigits {
public static void main(String[] args) {
System.out.println(sumDigits(1234));
}
public static int sumDigits(int n) {
if (n == 0) return 0;
return n % 10 + sumDigits(n / 10);
}
}
Explanation:
This recursive function calculates the sum of digits of the number 1234 by repeatedly extracting and summing the last digit.
Console Output:
10
Example 9: GCD Calculation
Concept:
The greatest common divisor (GCD) of two numbers is the largest number that divides both of them without leaving a remainder. This can be calculated using the Euclidean algorithm recursively.
public class GCDCalculation {
public static void main(String[] args) {
System.out.println(gcd(48, 18));
}
public static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
}
Explanation:
This recursive function calculates the GCD of 48 and 18 using the Euclidean algorithm, where the GCD of two numbers a and b is the same as the GCD of b and a % b.
Console Output:
6
Example 10: Merge Sort
Concept:
Merge sort is a divide-and-conquer algorithm that divides an array into halves, recursively sorts them, and then merges the sorted halves.
public class MergeSort {
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
mergeSort(arr, 0, arr.length - 1);
for (int num : arr) {
System.out.print(num + " ");
}
}
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
public static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; ++i) L[i] = arr[left + i];
for (int j = 0; j < n2; ++j) R[j] = arr[mid + 1 + j];
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
}
Explanation:
This recursive function sorts an array using merge sort, which divides the array into halves, recursively sorts each half, and merges the sorted halves.
Console Output:
5 6 7 11 12 13
