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?

1+2-3+4-5+6+7+89 = 101 1-2+3+4+5-6+7+89 = 101 1+23-4+5-6-7+89 = 101 123+4+56+7-89 = 101 12-3+4-5+6+78+9 = 101 1+23+4+5+67-8+9 = 101 1+2+34+56+7-8+9 = 101 1-2+34+5-6+78-9 = 101 1+2+3+45+67-8-9 = 101 12+34+5+67-8-9 = 101 Ten print operators will solve the problem — alex, Mar 26 '09 at 17:31
This was really fun to write in C#. It seems so easy on the surface. In the end, it took me a few hours to iron the bugs out and I had to find 2 additional libraries online. Thanks for the exercise. — Dinah, Mar 27 '09 at 14:59
There is another post on this subject: [http://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration](http://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration) — Miquel, Mar 26 '09 at 16:30

score 17 · Accepted Answer · answered Mar 26 '09 at 16:51

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.

This is correct and useful (and I voted it up), but I think recursion, if explained well, will be simpler. — Nick Johnson, Mar 26 '09 at 17:27
While it's true that the recursive formulation is a simple, tail-recursive function, the implementation environment available in the question is likely to make it ugly and not a good demonstration of recursion. — Thomas Kammeyer, Mar 27 '09 at 02:27

score 4 · Answer 2 · answered Mar 26 '09 at 16:28

4

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

answered Mar 26 '09 at 16:28

Mehrdad Afshari

414,610
91
852
789

I probably can and will, but that doesn't solve my curiosity about a non-recursive solution. – Steve Rowe Mar 26 '09 at 16:34
You can *always* write an iterative equivalent of a recursive solution but I don't think the iterative counterpart of your problem is as trival as the recursive one. – Mehrdad Afshari Mar 26 '09 at 16:36
It's pretty trivial, I'll post it in a few minutes – Seb Mar 26 '09 at 16:43
Oh, I've just seen he's 8, so it's not something he'd understand easily :( – Seb Mar 26 '09 at 16:46
1

Seb, don't underestimate kids by any means. :) – Mehrdad Afshari Mar 26 '09 at 17:08

score 2 · Answer 3 · answered Mar 26 '09 at 16:50

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.
}

?>

vartec · Answer 4 · 2009-03-26T16:35:16.900

1

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

edited Mar 26 '09 at 16:35

answered Mar 26 '09 at 16:29

vartec

131,205
36
218
244

It's not tail recursion, because there are three separate recursive calls. – Rob Lachlan Mar 26 '09 at 16:33

score 0 · Answer 5 · answered Mar 26 '09 at 16:29

0

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

answered Mar 26 '09 at 16:29

Richard

106,783
21
203
265

score 0 · Answer 6 · answered Mar 26 '09 at 16:30

0

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?

answered Mar 26 '09 at 16:30

Rob Lachlan

14,289
5
49
99

How do I solve this without recursion?

6 Answers6