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

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? ;)

Answer 2

Given the limited depth of recursion, an array can be used as a stack.

Answer 3

Of course it can be solved with simple iteration. You only have to convert the string to stack.

Answer 4

There is another post on this subject:

http://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration

Answer 5

It can be done iteratively, but not nearly as simply as this. More importantly, are you going to use this as an opportunity to teach your son about algorithm complexity?

Answer 6

You have 3 basic operations:

• Add (option "0");
• Substract (option "1");
• Do nothing (option "2");

So basically you have 3^8 possible solutions; just try them all.

This is PHP code, but includes converting numbers in other bases, which is something an 8 year-old boy probably wouldn't understand quickly. Maybe you can find the twist for this:

<?php

$limit = pow(3, 8);
for($op = 0; $op < $limit; $op++){
  // Get this operation.
  $op_base3 = base_convert($op, 10, 3);

  // Fill leading 0's.
  $op_base3 = str_pad($op_base3, 8, "0", STR_PAD_LEFT);

  // Here you get something like 00212120, which would say:
  // 1[+]2[+]3[nothing]4[-]5[nothing]6[-]7[nothing]8[+]9
  // That's: 1+2+34-56-78+9

  // Compute and if result's correct, output solution.
}

?>

Answer 7

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.