Recursive helper method

问题:

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, 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 ?

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

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

回答1:

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

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 high variable as a "countdown", by writing

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 public modifier was requested in the task description, but... maybe you'll receive some bonus points when you make your instructor aware of this flaw ;-)

回答2:

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.

回答3:

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.

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, combine it:

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 0 to initiate the process.

回答4:

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