Add numbers in a string with recursion in Java with substring

Solution 1:

If you do things recursively with a list of things, always think in the following pattern:

• handle the first element of the list
• handle the rest of the list using a recursive call

So in the case of "5 + 3 +2", split off 5 and "+" and then pass the rest ("3+2") to the same method again.

It's also far easier to remove the spaces before you start.

public static void main(String[] args) {
    String input = "5 + 3 + 2";
    //remove spaces:
    input = input.replaceAll(" +", "");
    int r = evaluate(input);
    System.out.println(r);
}

private static int evaluate(String s) {
    int operatorIndex = s.indexOf('+');
    if(operatorIndex == -1) {
        //no operator found, s is the last number
        //this is the base case that "ends" the recursion
        return Integer.parseInt(s);
    }
    else {
        //this is left hand side:
        int operand = Integer.parseInt(s.substring(0, operatorIndex));
        //this performs the actual addition of lhs and whatever rhs might be (here's where recursion comes in)
        return operand + evaluate(s.substring(operatorIndex+1));
    }
}

This code prints 10. It gets a more complex if you also want to support substraction, but you will figure it out.

Solution 2:

The "RHS" string ends up being something like " 3 + 2". Your job is not to get the 3. Your job is to recurse: Give that string to your own algorithm, trust that it works.

That's how recursion works: You assume your algorithm already works, and then you write it, calling yourself, with the additional rule that you can only call yourself with a 'simpler' case (because otherwise it'll never end), and that you write code to deal with the simplest case explicitly (which in this case would presumably be if I hand your method just a number. If I hand it "5", it needs to return 5, and not recurse).