Difficulty in keypad print using recursive approach

Question

I've been trying some recursion and backtracking problems. Done some questions like printing the subsequences, permutations, N-Queen which are base questions for these approaches. Now, what I've got to know is that we have to trust that the recursion will work and we just have to do our part of the problem and leave the remaining on the recursion.

Now, using this approach I was doing a problem in which we are given an array of keys of a keypad and we just have to print the combinations of the characters at particular keys(indices) of this array.

public class Keypad {

static String pad[] = { " ", ".+@$", "abc", "def", "ghi", "jkl" , "mno", "pqrs" , "tuv", "wxyz" };

static void keypad(String str, String result) {
    
    if(str.length() == 0) {
        System.out.println(result);
        return;
    }
    
    for(int i = 0; i < str.length(); i++) {
        char currKey = str.charAt(0);
        String key = pad[Integer.parseInt(""+currKey)];
        
        for(int j = 0; j < key.length(); j++) {
            char currChar = key.charAt(j);
            keypad(str.substring(1), result + currChar);
        }
    }
    
}
public static void main(String[] args) {
 String string = "12";
 keypad(string, "");
}
}

Required output -

.a .b .c +a +b +c @a @b @c $a $b $c (in newlines)

My output -

.a .b .c +a +b +c @a @b @c $a $b $c .a .b .c +a +b +c @a @b @c $a $b $c (in newlines)

Now, this is pretty straightforward without using recursion, directly using the loops to do it but here I am getting confused. What I did was I used the loop for the first input "1" and sent the other ones to the recursion by str.substring(1).

This code is partially working as it's printing the output twice, though I have a feeling that somewhere in the recursion tree, it is happening but I need to understand how to grasp this and how to find bugs in this type of program. Also, on a side note, this was my first question on stackOverFlow so if any suggestions are there related to posting questions or if anything is missing, do tell me. Thanks!

ggorlen · Accepted Answer · 2020-08-27T04:29:08.707

When you're working with recursion like this, keep in mind that the recursive calls are acting much like an outer loop, moving from 0...str.length and adding pad[str.charAt(0)] branches to the call tree per frame (that's a lot of branching). Intuitively, when you see an explosion of results, think about whether you have too many loops and recursive calls.

Secondly, think about whether the loops are traversing the right things. Since your recursive function is already counting over the characters in str, your inner loop for(int i = 0; i < str.length(); i++) is stepping outside of the stack frame to operate on parts of the string other than the current character. As you noted, you should let the recursive calls handle the rest of str and restrict the current call to operate only on a single character in str.

In the simplified algorithm (which is basically a Cartesian product), iterate over every character from pad[str.charAt(0)] and recurse on that character appended to the result, trimming the head character of str on every recursive step. Your base case is already correct.

static void keypad(String str, String result) {    
    if (str.length() == 0) {
        System.out.println(result);
        return;
    }

    String key = pad[Integer.parseInt("" + str.charAt(0))];
    
    for (int i = 0; i < key.length(); i++) {
        keypad(str.substring(1), result + key.charAt(i));
    }    
}

Other remarks:

As an efficiency boost, you may wish to add an index to the recursive call to avoid repeatedly calling substring.
Consider using an overloaded wrapper for the method so the client doesn't need to worry about the result parameter (or index parameter if you take the above tip).
Consider a more descriptive, action-oriented method name than keypad such as printKeypadProduct.
Instead of printing the results, best practice is to return a list so the caller can use the results in the rest of the program at their discretion.
Consider handling errors if keypad is called with an unparseable string like "foo".
Instead of making String pad[] a static class member, it might be worth making a parameter of keypad so that it can be specified dynamically. This has the added benefit of increased encapsulation so the method isn't dependent on a variable outside of its scope that might change unexpectedly, either in name or in contents. If you do keep it a class member, making it final is nice.

See also Iterative Cartesian Product in Java.

Though after researching more myself, I got the bug but your additional remarks made me think more about it. Can you please give me some in-depth details about the "index" optimization that can be made? — Nitish, Aug 27 '20 at 19:31
Instead of using `substring`, pass an index `keypad(String str, String result, int i)` and use `str.charAt(i)` and `i == str.length()` for the base case. The whole point of `substring` is to shorten the input string for recursive calls, but you can do the same thing without making copies of the string over and over again if you keep track of your location. — ggorlen, Aug 27 '20 at 20:41
Yes, you are right. These are some good optimizations that can be added. — Nitish, Aug 28 '20 at 08:08

Difficulty in keypad print using recursive approach

1 Answers1