WikiGalaxy
Recursion in Java
Understanding Recursion:
Recursion is a programming technique where a method calls itself to solve a problem. It divides the problem into smaller, more manageable sub-problems. Recursion is often used for tasks that can be broken down into repeated sub-tasks, such as navigating tree structures or solving complex mathematical problems like factorials and Fibonacci sequences.
Step 1: Define the base case to stop recursion.
Step 2: Define the recursive case that reduces the problem size.
Step 3: Ensure each recursive call progresses towards the base case.
Step 4: Test the recursive solution with various inputs.
public class Factorial {
public static int factorial(int n) {
if (n <= 1) return 1; // Base case
else return n * factorial(n - 1); // Recursive case
}
public static void main(String[] args) {
System.out.println("Factorial of 5: " + factorial(5));
}
}
Factorial Calculation:
The factorial of a number is the product of all positive integers less than or equal to that number. This example demonstrates a simple recursive approach to calculate the factorial of a number, where the base case is when the number is 1 or less.
Console Output:
Factorial of 5: 120
Fibonacci Sequence
Understanding Fibonacci Sequence:
The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. It is a classic example of a problem that can be solved using recursion.
Step 1: Define the base cases for the first two numbers (0 and 1).
Step 2: Use recursion to find the nth Fibonacci number by summing the two preceding numbers.
Step 3: Ensure the function progresses towards the base cases.
public class Fibonacci {
public static int fibonacci(int n) {
if (n <= 1) return n; // Base cases
else return fibonacci(n - 1) + fibonacci(n - 2); // Recursive case
}
public static void main(String[] args) {
System.out.println("Fibonacci of 5: " + fibonacci(5));
}
}
Fibonacci Calculation:
This example calculates the nth Fibonacci number using recursion, with base cases defined for the first two numbers in the sequence. The recursive case sums the two preceding numbers to find the nth number.
Console Output:
Fibonacci of 5: 5
Binary Search
Understanding Binary Search:
Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item until you've narrowed down the possible locations to just one.
Step 1: Compare the target value to the middle element of the array.
Step 2: If the target value matches the middle element, return its index.
Step 3: If the target value is less than the middle element, repeat the search on the left subarray.
Step 4: If the target value is greater than the middle element, repeat the search on the right subarray.
public class BinarySearch {
public static int binarySearch(int[] array, int target, int low, int high) {
if (low > high) return -1; // Base case
int mid = (low + high) / 2;
if (array[mid] == target) return mid; // Found target
else if (array[mid] > target) return binarySearch(array, target, low, mid - 1); // Search left
else return binarySearch(array, target, mid + 1, high); // Search right
}
public static void main(String[] args) {
int[] array = {1, 2, 3, 4, 5};
System.out.println("Index of 3: " + binarySearch(array, 3, 0, array.length - 1));
}
}
Binary Search Implementation:
This example demonstrates a recursive binary search algorithm. It efficiently finds the index of a target value within a sorted array by dividing the search space in half with each recursive call.
Console Output:
Index of 3: 2
Tower of Hanoi
Understanding Tower of Hanoi:
The Tower of Hanoi is a classic problem that involves moving a stack of disks from one peg to another, with the constraint that no disk may be placed on top of a smaller disk. It is a perfect example of a problem that can be solved recursively.
Step 1: Move n-1 disks from source to auxiliary peg.
Step 2: Move the nth disk from source to destination peg.
Step 3: Move the n-1 disks from auxiliary peg to destination peg.
public class TowerOfHanoi {
public static void solveHanoi(int n, char source, char auxiliary, char destination) {
if (n == 1) {
System.out.println("Move disk 1 from " + source + " to " + destination);
return;
}
solveHanoi(n - 1, source, destination, auxiliary);
System.out.println("Move disk " + n + " from " + source + " to " + destination);
solveHanoi(n - 1, auxiliary, source, destination);
}
public static void main(String[] args) {
solveHanoi(3, 'A', 'B', 'C');
}
}
Tower of Hanoi Solution:
This example demonstrates a recursive solution to the Tower of Hanoi problem. It involves moving disks between pegs using recursive calls to solve smaller sub-problems.
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
Palindrome Check
Understanding Palindrome Check:
A palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward (ignoring spaces, punctuation, and capitalization). Recursion can be used to check if a string is a palindrome by comparing the first and last characters and then recursively checking the substring.
Step 1: Compare the first and last characters of the string.
Step 2: If they match, recursively check the substring excluding the first and last characters.
Step 3: Return true if the entire string is checked, otherwise false.
public class Palindrome {
public static boolean isPalindrome(String s) {
return isPalindromeHelper(s, 0, s.length() - 1);
}
private static boolean isPalindromeHelper(String s, int left, int right) {
if (left >= right) return true; // Base case
if (s.charAt(left) != s.charAt(right)) return false;
return isPalindromeHelper(s, left + 1, right - 1); // Recursive case
}
public static void main(String[] args) {
System.out.println("Is 'racecar' a palindrome? " + isPalindrome("racecar"));
}
}
Palindrome Check Implementation:
This example demonstrates a recursive approach to check if a string is a palindrome. The recursion compares characters from the outermost to innermost positions, ensuring they match.
Console Output:
Is 'racecar' a palindrome? true
Permutations of a String
Understanding Permutations:
Permutations refer to all possible arrangements of a set of elements. Recursion can be used to generate permutations by swapping elements and recursively generating permutations of the remaining elements.
Step 1: Swap the current element with each subsequent element.
Step 2: Recursively generate permutations for the remaining elements.
Step 3: Backtrack by swapping back to restore the original order.
public class Permutations {
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 a, int i, int j) {
char temp;
char[] charArray = a.toCharArray();
temp = charArray[i];
charArray[i] = charArray[j];
charArray[j] = temp;
return String.valueOf(charArray);
}
public static void main(String[] args) {
String str = "ABC";
permute(str, 0, str.length() - 1);
}
}
Permutations Generation:
This example demonstrates a recursive approach to generate all permutations of a string by swapping characters and recursively generating permutations of the remaining string.
Console Output:
ABC ACB BAC BCA CAB CBA
Sum of Digits
Understanding Sum of Digits:
The sum of digits problem involves finding the sum of all digits in a given integer. Recursion can be used to solve this by isolating the last digit and recursively summing the remaining digits.
Step 1: Isolate the last digit of the number.
Step 2: Add it to the sum of the digits of the remaining number.
Step 3: Base case is when the number is reduced to 0.
public class SumOfDigits {
public static int sumDigits(int n) {
if (n == 0) return 0; // Base case
return n % 10 + sumDigits(n / 10); // Recursive case
}
public static void main(String[] args) {
System.out.println("Sum of digits of 123: " + sumDigits(123));
}
}
Sum of Digits Calculation:
This example demonstrates a recursive approach to calculate the sum of digits of a number by isolating the last digit and recursively summing the remaining digits.
Console Output:
Sum of digits of 123: 6
Power Calculation
Understanding Power Calculation:
The power calculation problem involves raising a number to a given power. Recursion can be used to solve this by multiplying the base by itself for the power times, reducing the power by one with each recursive call.
Step 1: Multiply the base by the result of the base raised to the power minus one.
Step 2: Base case is when the power is 0, returning 1.
public class PowerCalculation {
public static int power(int base, int exp) {
if (exp == 0) return 1; // Base case
return base * power(base, exp - 1); // Recursive case
}
public static void main(String[] args) {
System.out.println("2 raised to the power of 3: " + power(2, 3));
}
}
Power Calculation Implementation:
This example demonstrates a recursive approach to calculate the power of a number by multiplying the base by itself for the power times, reducing the power with each recursive call.
Console Output:
2 raised to the power of 3: 8
Reverse a String
Understanding String Reversal:
Reversing a string involves rearranging its characters in the opposite order. Recursion can be used to solve this by swapping characters from the ends towards the center.
Step 1: Swap the first and last characters of the string.
Step 2: Recursively reverse the substring excluding the first and last characters.
Step 3: Base case is when the string is reduced to a single character or empty.
public class ReverseString {
public static String reverse(String str) {
if (str.isEmpty()) return str; // Base case
return reverse(str.substring(1)) + str.charAt(0); // Recursive case
}
public static void main(String[] args) {
System.out.println("Reverse of 'hello': " + reverse("hello"));
}
}
String Reversal Implementation:
This example demonstrates a recursive approach to reverse a string by rearranging its characters in the opposite order, using recursion to handle the reversal of substrings.
Console Output:
Reverse of 'hello': olleh
