How do I solve this without recursion?

Question

I'm trying to help my son solve a math problem. This seems like a good opportunity to expose him to some programming. I can see the recursive solution but perhaps an iterative one would be easier to explain. The language he has learned so far has been SmallBasic which doesn't support recursion very well (no local variables). I'm not against teaching another language, but still want to understand if there is a good way to solve this without recursion.

The problem is this: Given the sequence of numbers 1 2 3 4 5 6 7 8 9, insert +'s and -'s between numbers so that the result adds up to 101. For instance, 1+23+4+5+67-8+9=101.

The recursive solution looks something like this:

next(total, number, nextNumber, sequenceString)
{
    //add
    next(total + number, ...);

    //subtract
    next(total - number, ...);

    //do nothing (multiply)
    next(total, number * 10, ...);
}

Is there an iterative solution to this that isn't terribly complex?

Answer 1

Consider the spaces between the numbers 1 2 3 4 5 6 7 8 9. There are 8 such interstitial spaces or slots.

Each such space can be filled by +, -, or nothing (indicating a longer number being formed).

That's three possibilities in each of eight slots. Assign digits to the three possible fillers as:

 0 --> +
 1 --> -
 2 --> (nothing)

Now every 8-digit trinary string corresponds to a solution. For examples:

 00000000 --> 1+2+3+4+5+6+7+8+9
 00000001 --> 1+2+3+4+5+6+7+8-9
 00000002 --> 1+2+3+4+5+6+7+89
 22222222 --> 123456789

Now write a simple loop that counts from 00000000 to 22222222 in trinary. Interpret each number along the way as a solution as above, stop as soon as you hit a solution yielding the target, 101, or report failure if you get to the end without hitting the target value.

There are 3^8 (exponent, not xor, or 3**8 for the fortranoids, or

 3*3*3*3*3*3*3*3

for the intensively literal-minded) possible solutions. That's only 6561; you can brute-force it this way quite handily.

Answer 2

Recursion is an important point in computer science. If your purpose of this is to teach your son, why don't you explain him recursion right now? ;)