When is a question about a puzzle, and when is it really about programming?

The following question was recently asked on Stack Overflow:

This is the problem: There are two players A and B. Player A starts and chooses a number in the range 1 to 10. Players take turn and in each step add a number in the range 1 to 10. The player who reaches 100 first wins.

In the program, player A is the user and player B is the computer. Besides that the computer must force a win whenever possible. For instance, if the player A reaches 88 at some point, the computer must choose 89, as this is the only way to force a win.

A user then voted to close the question, with the comment that it was about a logic or math problem rather than about programming.

Personally, I disagree with that. In fact, I think it's an unusually good example of a problem for learning to program.

Allow me to digress for a moment. The first step in learning to program is learning to take some algorithm, and transcribe it into the syntax of a chosen programming language. Now, it's certainly true that being able to express an algorithm in a chosen programming language is important. It's not just about syntax either. Just for example, expressing an algorithm well often involves knowing a great deal about the accepted idioms of that language as well. Nonetheless, the whole business of simply writing code is only the last step in a larger, usually much more involved process.

That larger, more involved process deals primarily with finding solutions to problems. Only once we've found a way to solve the problem can we write code in our chosen language to carry out that solution. Now, it's certainly true that in many cases, we want to use an iterative approach to a solution -- we don't expect the first code we write to be the final an ultimate solution to a real problem for real users. Nonetheless, when we write code, we need to write it to do something, and we need to decide on that something before we can write code to do it.

Now, the question already notes that 89 is a winning "position". That immediately leads us to two questions: 1) why is it a winning position? 2) Based on that, can we force a score of 89?

The answer to the first is simple: 89 is a winning position, because from there our opponent can't reach the goal of 100, but no matter what move he makes, in the subsequent move we can reach 100. That is so because 100-89 = 11. The smallest move the opponent can make is 1 and the largest is 10, so no matter what he chooses, the remainder will be between 1 and 10, and we can win.

That leads fairly directly to the next step: we can force a score of 89 if we can reach a score of 78 -- and we can force a score of 78 if we can reach a score of 67 (and so on, counting backwards by 11 until we reach 12 and finally 1.

Therefore, the first player can force a win if and only if he chooses 1 in his first turn. If he chooses anything larger, the second player can choose a number that gives a result of 12, guaranteeing himself the win.

This is a large part of why many of the better computer science programs have classically used (more or less) functional languages like Scheme, and emphasized recursion as a basic primitive. It's not really about recursion as a flow control primitive or anything like that. Yes, we've known for years that a for loop, while loop, etc. can be expressed via recursion (and likewise that anything we can do with recursion can also be done via other flow control primitives).

What's important isn't that recursion allows arbitrary flow control. What's important here is the way of thinking about and approaching the problem. Recursion just gives a simple and direct way to approach the problem: instead of solving for 100, if we know that 89 is a winning position we can solve for 89 instead. Note: we could just about as easily think of it mathematically. Instead of thinking of this as a case of recursion, we could think of it as an inductive proof. The steps I've outlined above are essentially the same as those for an inductive proof.

Now, it's certainly true that this approach isn't suitable for every programming problem. If you're dealing with something like: "why is this text field being computed as 134 pixels wide when it should be 135?", chances are recursion isn't going to enter into your thinking, and might not be a lot of help if it did.

Nonetheless, if you're trying to solve a problem, and can define one step toward a solution, chances are very good that an inductive/recursive approach will be useful in solving the whole problem. It's most obvious in a case like this where the problem and solution are mathematical, so we have a well-defined line from problem to solution, but it can also apply to quite a few other cases as well (including the previous problem about text width, which it's sometimes useful to think of in terms of "some arbitrary string followed by one character", and continue with shorter and shorter strings until we reach only one or two characters).