I am working on a function, countH(), that is supposed to count the amount of times a given number appears in a linked list. For some reason, I cannot get this to work recursively. I have tried a number of different solutions but I guess I can't get something in the correct place. Sorry if I am asking the question poorly, I struggle to understand recursion formatting sometimes.

Here is the function:

    public int count(int i) {
        return countH(first, i);
    }
    
    private int countH(Node front, int i) {  // TODO
        int cter = 0;
        if (front.next==null) {
            return 0;
        }
        if(front.item == i)
            cter  ;
        return countH(front, cter);
        
    }

This is a late version of my code, I'm sure it was a bit better before I messed with it a bunch to try to get it to work

Thanks!

CodePudding user response：

Every recursive implementation consists of two parts:

• base case - that represents a simple edge-case for which outcome is known in advance. For this task base case is a situation the given Node is null. Think about it this way: if a head-node is not initialed it will be null and that is the simplest edge-case that your method must be able to handle. And return value for the base case is 0.
• recursive case - a part of a solution where recursive calls a made and when the main logic resides. In your recursive case you need to check the value of a current node. If it matches the target value then the result returned by the method will be 1 countH(cur.next, i), otherwise it will be a result of the subsequent recursive call countH(cur.next, i).

Base case is always placed at the beginning of the method, followed by a recursive case.

And when you are writing a recursive part one of the most important things that you have to keep in mind is which parameters change from one recursive call to another, and which remains the same. In this case, changes only a Node, the target value i remains the same.

    public int count(int i) {
        return countH(first, i);
    }

    private int countH(Node cur, int i) { // `front` replaced by `cur`
        if (cur == null) { // not cur.next == null (it'll fail with exception if the head-node is null)
            return 0;
        }
//        int cter = 0; // this intermediate variable isn't needed, it could be incremted by 1 at most during the method execution
//        if(cur.item == i) 
//            cter  ;
//        return countH(cur, cter); // this line contains a mistake - variable `i` has to be passed as a parameter and `cter` must be added to the result returned by a recursive call

        return cur.item == i ? 1   countH(cur.next, i) : countH(cur.next, i);
    }

Suggestion

Follow the comments in the code. I've left your original lines in place so that will be easier to compare solutions. Also always try to come up will reasonable self-explanatory names for variables (as well as methods, classes, etc). For that reason, I renamed the parameter front to cur (short for current), because it's meant to represent any node, not first or any other particular node.

Side note

This statement is called a ternary operator or inline if statement

cur.item == i ? 1   countH(cur.next, i) : countH(cur.next, i);

And it's just a shorter syntax for the code below:

if (cur.item == i) {
    return 1   countH(cur.next, i);
} else {
    return countH(cur.next, i);
}

You could use either of these constructs in your code. The difference is only in syntax, both will get executed in presissely the same way.

CodePudding user response：

In a linked list, you should have one element and from that you get the value and the next element. So your item could look like (I am omitting getters, setters and exception handling):

class Item {
    Object value;
    Item next;
}

Then your counter for a specific value could look like

int count(Object valueToCount, Item list) {

    int result = 0;

    if (valueToCount.equals(list.value)) {
        result  ; // count this value
    }

    if (value.next != null) {
        result  = count(valueToCount, value.next) // add the count from remainder of the list
    }

    return result;
}