Example: Recursive Decoding Counter in Java

// Recursive Decoding Counter
public class Main {

    // Main function to initiate the recursive decoding process
    public static int countDecodingsRecursive(String s) {
        // Start the recursive helper function from the beginning of the string (index 0)
        return countDecodingsRecursiveHelper(s, 0);
    }

    // Helper function that performs the actual recursion
    private static int countDecodingsRecursiveHelper(String s, int index) {
        // Step 1: Base Case 1 - If we've reached the end of the string, it means we found one valid decoding.
        if (index == s.length()) {
            return 1;
        }

        // Step 2: Base Case 2 - If the current digit is '0', it cannot be decoded on its own.
        // It also cannot be part of a valid two-digit number (e.g., "01" is not 1, "00" is not valid).
        if (s.charAt(index) == '0') {
            return 0;
        }

        // Step 3: Count decodings by taking the current digit alone
        // Recursively call for the next position (index + 1)
        int count = countDecodingsRecursiveHelper(s, index + 1);

        // Step 4: Count decodings by taking the current digit and the next digit together
        // Check if there are at least two digits remaining and if they form a valid number (10-26)
        if (index + 1 < s.length()) {
            // Extract the two-digit number
            int twoDigitNum = Integer.parseInt(s.substring(index, index + 2));
            // If the two-digit number is within the valid range [10, 26]
            if (twoDigitNum >= 10 && twoDigitNum <= 26) {
                // Add the decodings from taking two digits together
                count += countDecodingsRecursiveHelper(s, index + 2);
            }
        }

        // Step 5: Return the total count for the current subproblem
        return count;
    }

    public static void main(String[] args) {
        // Test cases for the recursive approach
        System.out.println("--- Recursive Approach ---");
        System.out.println("Input: \"12\" | Possible decodings: " + countDecodingsRecursive("12"));       // Expected: 2 (AB, L)
        System.out.println("Input: \"226\" | Possible decodings: " + countDecodingsRecursive("226"));     // Expected: 3 (BBF, VF, BZ)
        System.out.println("Input: \"12345\" | Possible decodings: " + countDecodingsRecursive("12345")); // Expected: 3 (ABCDE, LCDE, AWDE)
        System.out.println("Input: \"10\" | Possible decodings: " + countDecodingsRecursive("10"));       // Expected: 1 (J)
        System.out.println("Input: \"0\" | Possible decodings: " + countDecodingsRecursive("0"));         // Expected: 0
        System.out.println("Input: \"1\" | Possible decodings: " + countDecodingsRecursive("1"));         // Expected: 1
        System.out.println("Input: \"27\" | Possible decodings: " + countDecodingsRecursive("27"));       // Expected: 1 (B7)
    }
}