Implementing recursion in Java

Question

Just to be clear, this is not a homework assignment, I study CS in my own time!

I recently purchased a book entitled '50 puzzles for logical thinking' by Charles Phillips. I started one of them and it occurred to me that I could solve the problem using recursion. Here's the (paraphrased) question:

Insert a mathematical operator (+, -, ÷, x) in each of the spaces to solve the equation:

6 _ 3 _ 5 _ 7 _ 4 _ 8 = 13

It is my understanding, that in order to solve this problem using recursion, I first need to identify a base case. However, I'm having trouble doing this.

So my question is, what is a possible base case and how should I begin to implement it? What could the recursive function look like (arguments, return type etc)? (code is helpful please)!

This is what I have so far: Nearly working I think

See my answer for an implementation

N.b. I'm using Java

I'm not sure that recursion is needed here. Given the speed of current computers, you could use a purely combinatorial approach (and try the 4^5 possibilities) — Basile Starynkevitch
– Basile Starynkevitch, Commented Jan 26, 2013 at 14:47
@BasileStarynkevitch: but recursion is a natural way to implement the combinatorial search. — Fred Foo
– Fred Foo, Commented Jan 26, 2013 at 14:48
4^5 is only 1024 - there shouldn't be any problem with going up to 16 places. Beyond that and you will have to wait quite some time. — nhahtdh
– nhahtdh, Commented Jan 26, 2013 at 14:51
Out of curiosity, are you supposed to be programming the solution to this, or are you just choosing to do so? I can see the solution to it after looking for a handful of seconds. — Ryan Stewart
– Ryan Stewart, Commented Jan 26, 2013 at 15:12

duffymo · Accepted Answer · 2013-01-26 14:48:58Z

2

I think the stopping condition should mean that the equation is satisfied: all the operators filled in, and the operations resulting in a proper equality.

I would express the equation as a parse tree, with the leaves as numbers and the parents as operators. A tree naturally lends itself to recursion, because it's a hierarchical data structure.

Make an operator assumption where the root operation is the minus sign, the right child is the desired value (13), and the left child is the left hand side. Add an operator, evaluate the tree, and backtrack until your stopping condition is met.

answered Jan 26, 2013 at 14:48

duffymo

310k46 gold badges376 silver badges570 bronze badges

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

Comments

Fred Foo · Accepted Answer · 2013-01-26 14:51:41Z

2

The base case is when all the blanks are filled in with operators. You can solve this problem using depth-first backtracking search:

algorithm dfs(i):
    if i == num_blanks:  # base case: filled in all the blanks
        if equation_solved():
            return the operators you filled in
    else:
        for op in (+, -, ÷, ×):
            blank[i] = op
            if dfs(i + 1) returns a solution:
                return that solution
            blank[i] = _     # restore to previous state

This is a recursive way of searching through the entire combinatorial space. (I hope this doesn't spoil the exercise for you; I wrote it in pseudocode to leave the implementation to you.)

edited Jan 26, 2013 at 14:51

answered Jan 26, 2013 at 14:46

Fred Foo

365k80 gold badges765 silver badges852 bronze badges

Comments

phant0m · Accepted Answer · 2013-01-26 15:44:53Z

1

You can think of it as a tree of decisions.

              6
        /    /    \    \
        +   -     *    /
        3                    Assuming you choose + for the first operator
/    /       \    \
+   -        *    /
5   5        5    5
    ^             ^
    6 + 3 - 5     6 + 3 / 5

You can then use a graph traversal algorithm such as DFS or BFS to check the result. Both are naturally recursive.

answered Jan 26, 2013 at 15:44

phant0m

17k6 gold badges52 silver badges84 bronze badges

Comments

Todd Davies · Accepted Answer · 2013-01-26 16:22:03Z

Here is the implementation I ended up with, but first an explanation of the solution to the problem:

The base case (as said by larsmans and Jan Dvorak) is when all the "_" are filled with operators (such as "+").
The function calls itself, adding another parameter each time until it reaches a base case that is incorrect (e.g. "6+3+5+7+4-8=13") or it has a correct answer.
If the base case is incorrect, then we keep popping up levels we get to a level with an operator we can change.

Here's the code:

class GapFill {

    private static String numbers; //E.g. 6_5_4=15
    private static String[] blank; //Array of operators to go in the blanks

    //Where:
    //p = plus
    //m = minus
    //d = divide
    //t = times
    private static String[] operators = {"p", "m", "d,", "t"};

    public static void main(String[] args) {
        numbers = args[0];
        blank = new String[numbers.split("_").length - 1];
        if(dfs(0)) { //If a solution was found
            int count = 0;
            while(numbers.indexOf("_")!=-1) {
                int index = numbers.indexOf("_");
                numbers = numbers.substring(0,index)+blank[count]+numbers.substring(index+1);
                count++;
            }
            System.out.println(numbers);
        }
    }

    private static boolean dfs(int i) {
        if(i == blank.length) {  //base case: filled in all the blanks
            return solveEquation();
        }
        for(String op : operators) {
            blank[i] = op;
            if(dfs(i + 1)) {
                return true;
            }
        }
        blank[i] = "_"; //restore to previous state
        return false;
    }

    private static boolean solveEquation() {
        String[] eachNumber = numbers.substring(0, numbers.indexOf("=")).split("_");
        String finalResult = numbers.substring(numbers.indexOf("=")+1, numbers.length());
        double currentResult = Double.parseDouble(eachNumber[0]);
        for(int i=1;i<eachNumber.length;i++) {
            String op = blank[i-1];
            if(op==operators[0]) {
                currentResult = currentResult + Integer.parseInt(eachNumber[i]);
            } else if(op==operators[1]) {
                currentResult = currentResult - Integer.parseInt(eachNumber[i]);
            } else if(op==operators[2]) {
                currentResult = currentResult / Integer.parseInt(eachNumber[i]);
            } else if(op==operators[3]) {
                currentResult = currentResult * Integer.parseInt(eachNumber[i]);
            }
        }
        return (currentResult==Integer.parseInt(finalResult));
    }

}

The output for java GapFill 6_3_5_7_4_8=13 is 6m3p5m7p4p8=13.

The "p,m,d,t" symbols are used instead of "+,-,÷,×" since the terminal doesn't like × or ÷

Collectives™ on Stack Overflow

Implementing recursion in Java

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related