Keeping count in a recursive Java method

Question

Here's what I'm trying to accomplish with this program: a recursive method that checks if the number of instances of a substring matches a specified amount of instances, returning a boolean.

Here's the issue I'm having with this particular recursive method: I'd like to be able to move the counter inside the recursive method body, however, I ran into the issue that the counter resets at each recursive call when it is in the method body. The only way I have been able to make it work is through the use of a static counter variable declared outside of the function body. Is there any other technique I can marshall in order to be able to situate the counter of the method in the method body so that this method may act as a "black box"?

Thanks for any advice or insights you can provide.

public class strCopies {

    //count instances of part and whole equality
    static int count = 0;

    public static boolean copies(String whole, String part, int check)
    {

        //check if current string length is valid
        if(whole.length() < part.length())
        {
            //check if check parameter equals part instances
            if(count == check)
            {
                return true;
            }
            else
            {
                return false;
            }
        }

        //check if current string value is an instance of part 
        if(whole.substring(0, 3).equals(part))
        {
            count++;
        }

        //recursive call
        return copies(whole.substring(1), part, check);

    }

    public static void main(String[] args)
    {
        System.out.println(copies("dogcatdog", "cat", 2));
    }
}

Sergey Kalinichenko · Accepted Answer · 2012-02-05 04:26:16Z

1

You are almost there: you should change the meaning of the check variable to the remaining number of matches, rather than the original number requested. Then you can rewrite the method without keeping an additional count at all, as follows:

public static boolean copies(String whole, String part, int check)
{

    //check if current string length is valid
    if(whole.length() < part.length())
    {
        //check if check parameter equals part instances
        if(check == 0)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    //check if current string value is an instance of part 
    if(whole.substring(0, 3).equals(part))
    {
        check--;
    }
    return return copies(whole.substring(1), part, check);
}

answered Feb 5, 2012 at 4:26

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

gryb Over a year ago

Thanks, I hadn't thought of this approach, but it is clearly the most elegant of all the proposed solutions.

Sergey Kalinichenko Over a year ago

@gryb You're welcome! The approach with decrementing the number of remaining steps is very common in recursive solutions, perhaps because the "ending condition" of the recursion looks somewhat more natural.

ose · Accepted Answer · 2012-02-05 04:26:09Z

0

You can pass the count as an argument to the recursive function, this way it will not be "reset" when the method is called.

public static boolean copies(String whole, String part, int check, int count)
{

    //check if current string length is valid
    if(whole.length() < part.length())
    {
        //check if check parameter equals part instances
        if(count == check)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    //check if current string value is an instance of part 
    if(whole.substring(0, 3).equals(part))
    {
        count++;
    }

    //recursive call
    return copies(whole.substring(1), part, check, count);

}

answered Feb 5, 2012 at 4:26

ose

4,0952 gold badges26 silver badges40 bronze badges

Comments

score 0 · Accepted Answer · 2012-02-05 04:31:07Z

public int countRecursive(String whole, String part){
    if(whole.length() < part.length()) return 0;
    if(part.length()==0) return -1; // ints can't express "Infinity" 
    // maybe you want to return -1 only if whole is not null, and something else if it is.       

    int count = 0;

    if(whole.substring(0, part.length()).equals(part))
        count = 1;
    return countRecursive(whole.substring(1), part) + count;
}

public boolean count(String whole, String part, int check){
    return countRecursive(whole, part) == check;
}

Note that this does away with the counter at the expense of creating a whole bunch of strings for each state. (You replace a single int with the length of each string given.) But then again, if you want performance then you shouldn't be using recursion for something like this. A simple for loop would do much nicer.

John Ericksen · Accepted Answer · 2012-02-05 04:31:23Z

You could add the counter to the method parameters as follows:

public class strCopies {

    public static boolean copies(String whole, String pargs, int check){
        return copies(whole, pargs, check, 0);
    }

    public static boolean copies(String whole, String part, int check, int count)
    {

        //check if current string length is valid
        if(whole.length() < part.length()) {
            //check if check parameter equals part instances
            if(count == check) {
                return true;
            }
            else {
                return false;
            }
        }

        //check if current string value is an instance of part
        if(whole.substring(0, 3).equals(part)) {
            count++;
        }

        //recursive call
        return copies(whole.substring(1), part, check, count);

    }

    public static void main(String[] args) {
        System.out.println(copies("dogcatdog", "dog", 2));
    }
}

Liran Orevi · Accepted Answer · 2012-02-05 04:35:34Z

0

The simple version:

Create a class that contain the counter. Initialize it on your main. Pass its reference to the function.

Another idea:

Create a singleton class with a static counter and your function X. Inside its constructor add one to its counter and call function X.

Then instead of running your function like you did before, "create" that class, thus increasing the counter and calling the function.

The neat thing is you can inherit that class and redefine X to whatever you choose at a latter stage, so you get this general class that counts on each activation of a function.

edited Feb 5, 2012 at 4:35

answered Feb 5, 2012 at 4:25

Liran Orevi

4,9438 gold badges49 silver badges65 bronze badges

Comments

Josh Crozier · Accepted Answer · 2013-11-03 17:15:19Z

0

Not sure what is your recursive method doing. However, to maintain a counter, you can pass it as an argument to your recursive method.

public boolean copies(String whole, String part, int check, int count) {

    // your code here....

    if(whole.substring(0, 3).equals(part))
    {
        count++;
    }

    //recursive call
    return copies(whole.substring(1), part, check, count);
}

When you make first call to your copies method, you'll need to pass 0 to your count.

edited Nov 3, 2013 at 17:15

Josh Crozier

242k56 gold badges401 silver badges316 bronze badges

answered Feb 5, 2012 at 4:27

Husain Basrawala

1,75115 silver badges22 bronze badges

Collectives™ on Stack Overflow

Keeping count in a recursive Java method

6 Answers 6

2 Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

2 Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related