Java 递归辅助方法

Recursive helper method

提问by Peter

i cant find the right solution for this exercise, here is the task:

我找不到此练习的正确解决方案，这是任务：

---

---

(Occurrences of a specified character in an array) Write a recursive method that finds the number of occurrences of a specified character in an array. You need to define the following two methods.The second one is a recursive helper method.

（数组中指定字符的出现次数）编写一个递归方法，查找指定字符在数组中的出现次数。您需要定义以下两个方法。第二个是递归辅助方法。

public static int count(char[] chars, char ch)

public static int count(char[] chars, char ch)

public static int count(char[] chars, char ch, int high)

public static int count(char[] chars, char ch, int high)

Write a test program that prompts the user to enter a list of characters in one line, and a character, and displays the number of occurrences of the character in the list.

编写一个测试程序，提示用户在一行中输入一个字符列表和一个字符，并显示该字符在列表中出现的次数。

---

---

1) I can solve it only if I add another parameter (int index) but how can I do it without adding another parameter or using for loop ?

1）只有添加另一个参数（int index）才能解决它，但是如何在不添加另一个参数或使用for循环的情况下解决它？

2)Why is the helper method there? I don't understand the purpose of helper methods in recursion.

2）为什么会有辅助方法？我不明白递归中辅助方法的目的。

Here is my solution:

这是我的解决方案：

package occurencesinarray;

import java.util.Scanner;

public class Start {
public static void main(String[] args){
    System.out.println("Enter few characters: ");
    Scanner scan = new Scanner(System.in);
    String s = scan.nextLine();
    char[] chars = new char[s.length()];
    for(int i = 0; i < s.length(); i++){
        chars[i] = s.charAt(i);
    }
    System.out.println("Enter desired character: ");
    char ch = scan.nextLine().charAt(0);

    System.out.println(count(chars, ch));
}

public static int count(char[] chars, char ch){
    return count(chars, ch, 0, 0);
}

public static int count(char[] chars, char ch, int high, int index){
    if(index == chars.length){
        return high;
    }
    if(chars[index] == ch){
        return count(chars, ch, high + 1, index + 1);
    } else{
        return count(chars, ch, high, index + 1);
    }
}
}

采纳答案by Marco13

As AllenKll already pointed out, the highvalue should probably take the role that you intended for your index. You have been counting the number of occurances in the highvariable, but this counting can be "hidden" in the recursion.

正如 AllenKll 已经指出的那样，该high值可能应该扮演您打算为您的index. 您一直在计算high变量中出现的次数，但这种计数可以在递归中“隐藏”。

The purpose of these "helper" methods for recursion in general is exactly that: They usually have (at least) one additional parameter that somehow describes how far the recursion has already proceeded or how far it still has to proceed. As an example for the latter: You could also have used the highvariable as a "countdown", by writing

这些递归的“辅助”方法的目的通常是这样的：它们通常（至少）有一个附加参数，以某种方式描述递归已经进行了多远或还需要进行多远。作为后者的一个例子：你也可以使用high变量作为“倒计时”，通过写

public static int count(char[] chars, char ch)
{
    return count(chars, ch, chars.length - 1);
}

public static int count(char[] chars, char ch, int high)
{
    if (high == -1)
    {
        return 0;
    }
    if (chars[high] == ch)
    {
        return 1 + count(chars, ch, high - 1);
    }
    return count(chars, ch, high - 1);
}

Of course, one could only offer the helper method. Instead of calling

当然，只能提供辅助方法。而不是打电话

count(chars, ch);

you could ask the user to call

你可以要求用户打电话

count(chars, ch, 0);

But the problem here is that this method may be misused: When then user passes a wrong value as the last parameter, then the method will not work.

但是这里的问题是这个方法可能会被误用：当用户将错误的值作为最后一个参数传递时，该方法将不起作用。

Note: This whole "helper method" thing only makes sense when the helper method is private. When it is public, the user may still call the wrong method. I see that the publicmodifier was requested in the task description, but... maybe you'll receive some bonus points when you make your instructor aware of this flaw ;-)

注意：整个“辅助方法”只有在辅助方法是private时才有意义。当它是 时public，用户仍然可能调用错误的方法。我看到public在任务描述中要求了修改器，但是......当你让你的导师意识到这个缺陷时，你可能会得到一些加分;-)

回答by AllenKll

How about this:

这个怎么样：

high represents the index

高代表指数

public static int count(char[] chars, char ch, int high){
    if(high == chars.length){
        return 0;
    }
    if(chars[index] == ch){
        return count(chars, ch, high + 1) + 1;
    } else{
        return count(chars, ch, high + 1);
    }
}

The helper method is so the caller doesn't need to know about the "high" parameter. In another language, such as C where you can have default parameters, it wouldn't be necessary.

辅助方法是这样调用者不需要知道“高”参数。在另一种语言中，例如 C，您可以使用默认参数，则没有必要。

回答by Bohemian

Firstly, your helper (recursive) method should be private, not public. It requires knowledge of how it works to be able to call it correctly. This goes against good software design, which says that the implementation is not important, as long as its contract is obeyed.

首先，您的助手（递归）方法应该是private，而不是public。它需要了解它是如何工作的才能正确调用它。这与良好的软件设计背道而驰，后者认为只要遵守合同，实现并不重要。

The first method is just the public-facing facade that sets up the initial conditions (parameters) of the recursive method. The real action is in the recursive method.

第一种方法只是设置递归方法的初始条件（参数）的面向公众的外观。真正的动作是在递归方法中。

Recursive (helper) methods usually have three things that must be determined (and coded):

递归（辅助）方法通常具有必须确定（和编码）的三件事：

• The initial state
• The terminating condition
• How to advance to the next state

• 初始状态
• 终止条件
• 如何前进到下一个状态

The initial state is usually handled by a facade method, as in your case.

初始状态通常由外观方法处理，就像您的情况一样。

The terminating state is typically the first line of code in the method, and causes an immediate return (also the case for your case)

终止状态通常是方法中的第一行代码，并导致立即返回（您的情况也是如此）

If the terminating condition is not met, the state (and/or calculation) may be saved locally to contribute to the returned value, then the method calls itself using parameters that advance the state to the next position. The result of the self-call is returned, possibly combined with data from the saved state.

如果不满足终止条件，则可以在本地保存状态（和/或计算）以贡献于返回值，然后该方法使用将状态推进到下一个位置的参数调用自身。返回自调用的结果，可能与来自保存状态的数据相结合。

In your case, you are passing the local state through to the next call. Don't do this. Instead, combineit:

在您的情况下，您将本地状态传递到下一个调用。不要这样做。相反，结合它：

public static int count(char[] chars, char ch, int index) {
    // Test for terminating condition
    if (index == chars.length) {
        return 0;
    }
    // return 1 if ch matches (0 otherwise) plus count from the remaining input
    return (chars[index] == ch ? 1 : 0) + count(chars, ch, index + 1);
}

And call it with an index of 0to initiate the process.

并使用索引调用它0以启动该过程。

回答by suavidas

public static int count(char[] chars, char ch)
{
   return count(chars, ch, 0);
}

public static int count(char[] chars, char ch, int high)
{
    int count = high;
    if chars.size()== 0
    {
       return count;
    }
    else if(chars.indexOf(0) == ch)
    {
       count++;
    }

    return count(Arrays.copyOfRange(charList, 1, charList.size()), ch, count);
}