英文:
Difficulty in keypad print using recursive approach
问题
我一直在尝试一些递归和回溯问题。完成了一些问题，比如打印子序列、排列、N皇后，这些都是这些方法的基本问题。现在，我知道的一件事是，我们必须相信递归会起作用，我们只需要完成问题的一部分，把剩下的交给递归处理。
现在，使用这种方法，我正在解决一个问题，给定一个按键的数组，我们只需要打印这个数组中特定按键（索引）的字符组合。
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, "");
}
}
期望输出：
.a .b .c +a +b +c @a @b @c $a $b $c (每行一个)
我的输出：
.a .b .c +a +b +c @a @b @c $a $b $c .a .b .c +a +b +c @a @b @c $a $b $c (每行一个)
现在，这个问题很简单，不使用递归，直接使用循环可以解决，但我在这里感到困惑。我做的是，我对第一个输入"1"使用循环，然后将其他输入通过`str.substring(1)`发送到递归中。
这段代码部分有效，因为它打印了两次输出，虽然我有一种感觉，在递归树的某个地方，它发生了，但我需要理解如何抓住这一点，以及如何在这种类型的程序中找到错误。
另外，顺便说一句，这是我在stackOverFlow上的第一个问题，所以如果有关于发布问题的建议，或者是否有任何遗漏的地方，请告诉我。谢谢！
<details>
<summary>英文:</summary>
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!
</details>
# 答案1
**得分**: 0
当您像这样使用递归时，请记住递归调用在行为上很像外部循环，从 `0...str.length` 移动，并在每个帧上添加 `pad[str.charAt(0)]` 分支到调用树中（这是很多分支）。直观地说，当您看到结果的爆炸时，请考虑是否有太多的循环和递归调用。
其次，请考虑循环是否正在遍历正确的内容。由于您的递归函数已经在 `str` 的字符上进行了计数，您的内部循环 `for(int i = 0; i < str.length(); i++)` 正在超出堆栈帧，以处理除当前字符以外的字符串部分。正如您所指出的，应该让递归调用处理 `str` 的其余部分，并限制当前调用仅在 `str` 中的单个字符上操作。
在简化的算法中（基本上是一个[笛卡尔积](https://en.wikipedia.org/wiki/Cartesian_product)），从 `pad[str.charAt(0)]` 的每个字符开始迭代，并在结果上进行递归，每个递归步骤都删除 `str` 的头字符。您的基本情况已经是正确的。
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));
}
}
其他备注：
- 作为提高效率的方式，您可能希望在递归调用中添加一个索引，以避免重复调用 `substring`。
- 考虑为方法添加一个重载的包装器，以便客户端无需担心 `result` 参数（或索引参数，如果您使用了上面的提示）。
- 考虑使用比 `keypad` 更具描述性和动作性的方法名称，比如 `printKeypadProduct`。
- 最佳实践是不要直接打印结果，而是返回一个列表，以便调用者可以根据需要在程序的其他部分使用结果。
- 考虑在使用无法解析的字符串（如 `"foo"`）调用 `keypad` 时处理错误。
- 与其将 `String pad[]` 设为 `static` 类成员，不如将其作为 `keypad` 的参数，这样可以动态指定。这还带来了增加封装性的额外好处，使方法不依赖于其范围外可能会意外更改的变量，无论是名称还是内容。如果您将其保留为类成员，将其设置为 `final` 是一个好的做法。
另请参阅 [在 Java 中进行迭代的笛卡尔积](https://stackoverflow.com/questions/1719594/iterative-cartesian-product-in-java)。
<details>
<summary>英文:</summary>
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](https://en.wikipedia.org/wiki/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](https://stackoverflow.com/questions/1719594/iterative-cartesian-product-in-java).
</details>
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论