Exploring Recursive Algorithms in Java

Recursive algorithms are a powerful tool in computer science, allowing us to solve complex problems by breaking them down into smaller, more manageable subproblems. In this blog post, we will explore three different recursive algorithms in Java: String Permutation, Maze Path Problem (Only Right and Down), and Maze Path Problem with Diagonal Options.

Problem 1: String Permutation

Problem Statement

Given a string, our goal is to generate all possible permutations of its characters. For instance, if the input string is “abc,” the expected output would be:

abc
acb
bac
bca
cab
cba

Solution Approach

To generate permutations using branch recursion, we can define a recursive helper function. The function takes the input string, a prefix (initially empty), and a list to store the permutations.

1. If the input string is empty, we have found a complete permutation. We add the prefix to the result list.
2. Otherwise, for each character in the input string:

• We choose the character as the next element in the permutation.
• We generate the remaining string by removing the chosen character.
• We recursively call the helper function with the remaining string and the updated prefix.
• This allows us to explore all possible combinations of characters.

Here’s the code implementation:

import java.util.ArrayList;
import java.util.Base64;
import java.util.List;
import java.util.Scanner;

public class StringPermutation {
    public static void perm(String str, String prefix, List<String> result) {
        if (str.length() == 0) {
            result.add(prefix);
            return;
        }

        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            String remaining = str.substring(0, i) + str.substring(i + 1);
            perm(remaining, prefix + ch, result);
        }
    }

    public static void main(String[] args) {
        String encodedCreatedBy = "S3VzaGFncmEgT2poYQ==";
        String createdBy = decryptBase64(encodedCreatedBy);
        System.out.println("Coded by " + createdBy);

        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter a string: ");
        String input = scanner.nextLine();

        List<String> permutations = new ArrayList<>();
        perm(input, "", permutations);

        System.out.println("Permutations:");
        for (String permutation : permutations) {
            System.out.println(permutation);
        }

        scanner.close();
    }

    private static String decryptBase64(String encodedString) {
        byte[] decodedBytes = Base64.getDecoder().decode(encodedString);
        return new String(decodedBytes);
    }

}

Problem 2: Maze Path Problem (Only Right and Down)

Problem Statement

Given a maze with a starting point and an ending point, we need to find all possible paths from the starting point to the ending point. In this variation, we can only move right or down in the maze.

Solution Approach

To solve the maze path problem, we can use a recursive approach:

1. If we are at the ending point, we have found a valid path. We print the path and return.
2. If we can move down from the current position (row < endRow), we make a recursive call by moving down.
3. If we can move right from the current position (col < endCol), we make a recursive call by moving right.
4. By making these recursive calls, we explore all possible paths from the starting point to the ending point.

Here’s the code implementation:

import java.util.Base64;
import java.util.Scanner;

public class MazePath {
    public static void mazePathProblem(int row, int col, int endRow, int endCol, String result) {
        if (row == endRow && col == endCol) {
            System.out.println(result);
            return;
        }

        if (row < endRow) {
            mazePathProblem(row + 1, col, endRow, endCol, result + "D");
        }

        if (col < endCol) {
            mazePathProblem(row, col + 1, endRow, endCol, result + "R");
        }
    }

    public static void main(String[] args) {
        String encodedCreatedBy = "S3VzaGFncmEgT2poYQ==";
        String createdBy = decodeBase64(encodedCreatedBy);
        System.out.println("Coded by " + createdBy);

        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the starting row: ");
        int startRow = scanner.nextInt();
        System.out.print("Enter the starting column: ");
        int startCol = scanner.nextInt();
        System.out.print("Enter the ending row: ");
        int endRow = scanner.nextInt();
        System.out.print("Enter the ending column: ");
        int endCol = scanner.nextInt();
        mazePathProblem(startRow, startCol, endRow, endCol, "");

        scanner.close();
    }

    private static String decodeBase64(String encodedString) {
        byte[] decodedBytes = Base64.getDecoder().decode(encodedString);
        return new String(decodedBytes);
    }

}

Problem 3: Maze Path Problem with Diagonal Options

Problem Statement

Given a maze with a starting point and an ending point, we need to find all possible paths from the starting point to the ending point. In this variation, we can move right, down, or diagonally.

Solution Approach

To solve the maze path problem with diagonal options, we can modify the previous solution by adding an additional recursive call for diagonal movement:

1. If we are at the ending point, we have found a valid path. We print the path and return.
2. If we can move down from the current position (row < endRow), we make a recursive call by moving down.
3. If we can move right from the current position (col < endCol), we make a recursive call by moving right.
4. If we can move diagonally (row < endRow && col < endCol), we make a recursive call by moving diagonally.
5. By making these recursive calls, we explore all possible paths from the starting point to the ending point.

Here’s the code implementation:

import java.util.Base64;
import java.util.Scanner;

public class MazePathDiagonal {
    public static void mazePathProblem(int row, int col, int endRow, int endCol, String result) {
        if (row == endRow && col == endCol) {
            System.out.println(result);
            return;
        }

        if (row < endRow) {
            mazePathProblem(row + 1, col, endRow, endCol, result + "D");
        }

        if (col < endCol) {
            mazePathProblem(row, col + 1, endRow, endCol, result + "R");
        }

        if (row < endRow && col < endCol) {
            mazePathProblem(row + 1, col + 1, endRow, endCol, result + "X");
        }
    }

    public static void main(String[] args) {
        String encodedCreatedBy = "S3VzaGFncmEgT2poYQ==";
        String createdBy = decodeBase64(encodedCreatedBy);
        System.out.println("Coded by " + createdBy);

        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the starting row: ");
        int diagonalStartRow = scanner.nextInt();
        System.out.print("Enter the starting column: ");
        int diagonalStartCol = scanner.nextInt();
        System.out.print("Enter the ending row: ");
        int diagonalEndRow = scanner.nextInt();
        System.out.print("Enter the ending column: ");
        int diagonalEndCol = scanner.nextInt();
        mazePathProblem(diagonalStartRow, diagonalStartCol, diagonalEndRow, diagonalEndCol, "");

        scanner.close();
    }

    private static String decodeBase64(String encodedString) {
        byte[] decodedBytes = Base64.getDecoder().decode(encodedString);
        return new String(decodedBytes);
    }

}

Conclusion

In this blog post, we explored three different recursive algorithms in Java: String Permutation, Maze Path Problem (Only Right and Down), and Maze Path Problem with Diagonal Options. We discussed the problem statements and the corresponding solution approaches for each problem.

Recursive algorithms provide elegant solutions to a wide range of problems, allowing us to break them down into smaller, more manageable subproblems. By understanding these examples and experimenting with different inputs, you can gain a deeper understanding of recursion and apply it to solve various other problems.

I hope you found this blog post informative and helpful. Keep exploring the fascinating world of recursive algorithms.

Thanks for Reading ❤❤