Java: Simple Recursion Issue

Question

I'm extremely new to the whole idea of recursion, and it's blowing my mind a bit to be honest. I'm trying to turn this function I wrote into a recursive one...

public static int to_number(String s)
{
    int total = 0;
    int n=s.length();
    for(int i = 0 ; i < n ; i++) { 
        char c = s.charAt(i);
        if (Character.isDigit(c)){
            int value=Character.getNumericValue(c);
            total +=value;
        }
    }
    System.out.println(total);
    return total;
}

It reads in a string, such as "3aaa6a3", iterates through the string, if the char is a digit, it adds it to total, and so on. What I have so far...

    public static int to_number(String s)
{
    int total = 0;
    int n=s.length();
    int i=0;
    if (i == n){
        return 0; //if gone through the whole string
    }
    char c = s.charAt(i);
        if (Character.isDigit(c)){
            int value=Character.getNumericValue(c);
            total +=value;
        }

    System.out.println(total);
    i++;
    to_number(); //trying to call the same function
    return total;
}

I feel like I'm close, but just not getting it. Thanks for your time and effort!

At first glance that's not going to compile. You're trying to call the to_number(String) method with no parameters. — azurefrog
– azurefrog, Commented Oct 23, 2015 at 20:14
@dguay passing s will cause infinite recursion. The OP needs to pass a substring of s. — azurefrog
– azurefrog, Commented Oct 23, 2015 at 20:15
You should pass the string and current index that you are looking at to fetch the character to the function. Start with index = 0 and increment in each call. That way if ( i == n) will make sense. You should be able to proceed with this tip — user2647463
– user2647463, Commented Oct 23, 2015 at 20:17

Andreas · Accepted Answer · 2015-10-23 20:17:30Z

1

Not gonna give you the code, but as a recursive function, you want to process the first character of the input string, then call yourself with the remaining string, i.e. to_number(s.substring(1)), and combine the result. Recursion ends when input string is empty.

answered Oct 23, 2015 at 20:17

Andreas

160k13 gold badges164 silver badges262 bronze badges

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

Comments

AbtPst · Accepted Answer · 2015-10-23 20:26:56Z

0

try this

public void intToNum(String s, int total[])
{

     if(s.isEmpty())
        return;

     char c = s.charAt(0);

if (Character.isDigit(c)){
            int value=Character.getNumericValue(c);
            total[0] +=value;
        }

intToNum(s.substring(1),total);

}

and in your main, call the function as

int [] total = new int[1];

intToNum(input,total);

System.out.println(total[0]);

or another approach is

public int intToNum(String s) {

     if(s.isEmpty())
        return 0;

     char c = s.charAt(0);

if (Character.isDigit(c)){

            int value=Character.getNumericValue(c);

            return value + intToNum(s.substring(1));
        }

return intToNum(s.substring(1));

}

edited Oct 23, 2015 at 20:26

answered Oct 23, 2015 at 20:17

AbtPst

8,03822 gold badges97 silver badges187 bronze badges

9 Comments

azurefrog Over a year ago

wouldn't it be much easier to simply pass the total back as the output of the method?

rby Over a year ago

why is total an array?

Bob Over a year ago

Yes, I was curious as to why you put total as an array?

Bob Over a year ago

wouldn't you have to add an array to the call of intToNum as well and not just a string?

Bob Over a year ago

Okay I see what ya did now, not the way I was thinking of doing it, but hey its a start to my recursive learning! Thanks I really appreciate it!

|

brimborium · Accepted Answer · 2015-10-23 21:19:37Z

This answer contains the solution. Just look at it when you are stuck. I also encourage you to read and understand the code instead of just copying it. This is one of the most important concepts in programming, so make sure you understand it and are familiar with it. :)

How it works: The method receives a string. If the string is longer than 1 character, the method splits it in half, calls itself on the two substrings and adds the two results. Those calls will do the same thing, until the string fragments are only 1 (or 0) characters long. In that case, it just returns their value (or 0, if there is no value).

public class RecursionVsIteration {
    public static void main(String[] args) {
        String str = "2.938fyfh0293urhp2398rpod8723uoihr98y";
        System.out.println("Iterative: " + toNumberIterative(str));
        System.out.println("Recursive: " + toNumberRecursive(str));
    }

    public static int toNumberIterative(String s) {
        int total = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int value = Character.getNumericValue(c);
                total += value;
            }
        }
        return total;
    }

    public static int toNumberRecursive(String s) {
        int n = s.length();
        // termination criteria
        if (n == 0) { // emtpy string
            return 0;
        }
        if (n == 1) { // on character string
            char c = s.charAt(0);
            return Character.isDigit(c) ? Character.getNumericValue(c) : 0;
        }

        // recursive call (split the string in half and call the method on both substrings)
        return toNumberRecursive(s.substring(0, n / 2)) + toNumberRecursive(s.substring(n / 2, n));
    }
}

Collectives™ on Stack Overflow

Java: Simple Recursion Issue

3 Answers 3

Comments

9 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

9 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related