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

Answer 1

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.

Answer 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.)