递归辅助方法

Question

我无法找到此练习的正确解决方案，以下是任务：

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

公共静态int计数（char[]chars，char ch）

公共静态int计数（char[]chars， char ch， int high）

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

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

2）为什么有helper方法？我不明白helper方法在递归中的目的。

以下是我的解决方案：

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);
    }
}
}

Answer 1

首先，您的助手（递归）方法应该是私有的，而不是公共的。它需要知道它是如何工作的，才能正确地调用它。这与良好的软件设计背道而驰，即只要遵守合同，实现就不重要。

第一个方法就是面向公众的facade，它设置递归方法的初始条件（参数）。实际操作是递归方法。

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

• 初始状态

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

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

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

在您的情况下，您正在将本地状态传递给下一个调用。不要这样做。相反，请将其合并：

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);
}

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

Answer 2

这个怎么样：

高代表指数

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);
    }
}

helper方法是这样的，调用方不需要知道“high”参数。在另一种语言中，如C语言，您可以使用默认参数，这是不必要的。

Answer 3

正如AllenKll已经指出的那样，高值很可能会扮演您为索引指定的角色。您一直在计算高变量中发生的次数，但此计数可以在递归中“隐藏”。

一般来说，这些递归“助手”方法的目的正是：它们通常（至少）有一个附加参数，以某种方式描述递归已经进行了多远或还需要进行多远。作为后者的示例：您也可以使用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);
}

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

count(chars, ch);

您可以要求用户拨打

count(chars, ch, 0);

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

注意：只有当helper方法是私有的时，整个“helper方法”才有意义。当它是公共的时，用户仍然可能调用错误的方法。我看到任务描述中请求了public修饰符，但是。。。当您让您的指导老师意识到此缺陷时，您可能会获得一些加分；-）