Recurring Drama

The continuing saga of recursive implementations of Bowling, email from our fans, and a refactoring of my Java code.

Remarks on Recursive Implementations

A few people have taken me to task for my remarks that recursive implementations are, in my opinion, difficult to understand. Isaac Gouy, always a delight to encounter, opines on the XP list:

Soon 2 years will have passed since someone explained to you what “the infamous Bowling Game” might look like in a functional programming language, but that was in a newsgroup discussion not on stage :-)

http://groups.google.com/group/comp.object/msg/b8dfcb9fcaa45b4e
http://groups.google.com/group/comp.object/msg/f37aea0bf095cc72

I seem to remember learning about recursive functions 30 years ago, in the second week of a Pascal programming course, so it’s a little puzzling to me that a software developer would say “Recursive methods tend to be confusing, in my opinion.”

I guess I’ll just let that stand as it is.

I also heard privately from Tom Moertel on the subject, also expressing the notion that recursion is not the culprit. He offers:

The problem with the other implementations isn’t that they are recursive, but that they use an unreliable termination test. Thus, I wouldn’t characterize this flaw as being attributable to recursion. (I hope you will update your article to make this clear.)

Rather, the culprit is that these implementations rely upon a particular sequence of final rolls to determine when to end the scoring process. As you have pointed out, the final rolls, when considered by themselves, can be ambiguous. Any implementation that relied upon them, recursive or not, would fail the ninth-frame-strike test.

The problem with the “other” implementations, as Tom suggests, certainly is that they have improper termination conditions. I think that concern is more endemic to recursive solutions than to iterative ones. In iterative solutions, we tend to loop very simply, over some integer sequence (1 to number of frames, for example), or over all the elements of a list. In recursive ones, the approved style is to recur until some termination condition arises. When all we’re doing is processing a list, this can generate the same result. When we really should do something exactly ten times, it’s common in writing recursive approaches to try to terminate on some condition in the structure we’re processing, not on a count. Tom’s implementation, it seems to me, is not typical of the way one tries to program with recursive algorithms.

(His implementation has the advantage of being the one that works, mind you, which is rather an important consideration by any standards!)

Tom goes on to say:

Also, you brought up an interesting hypothesis: “Pit hypothesizes, and I’m inclined to agree, that you simply must deal with the tenth frame differently in all these recursive versions.” I should point out that my implementation serves as a counterexample to this hypothesis: it is recursive and yet deals with the tenth frame the same as the rest.

I can’t entirely agree with Tom here. His implementation does in fact deal with the tenth frame differently. If it did not, it would have the same defect that Pit discovered, dealing with 10, 2,3 at the end of the game. One way or another, any implementation has to recognize that it should not treat the trailing 2,3 as a new frame, but should instead stop.

Stop Marker

Dan Mead reports that he has a version that doesn’t use a frame count, but that has a stop marker of 0,0 on the end of the list, and that it is passing the tests. I haven’t seen it yet, but it seems to me that with the stop marker added, at least some of the other termination conditions are impossible, and I also grant that I don’t see why the addition of an empty frame would make the program work.

Now I suppose it could just be a personal disability not to be able to see why that sort of a thing would work. Certainly adding a stop marker to a list is a common recursive programming technique. But frankly, I don’t think it’s just a personal problem. I’ve been writing recursive code, in many languages, since the early 60’s. Wrote a master’s thesis on list processing, as a matter of fact. Still, perhaps I’m just past it.

I would bet, though, that if we were to take some set of problems that can be solved in a natural fashion both recursively and iteratively, and had a bunch of programmers write both versions, they would have more trouble with the recursive ones, on the average. And I’d bet that if we had people read the resulting programs, they would have more trouble understanding the recursive implementations, and convincing themselves that they work.

I could, of course, be wrong — I frequently am. But I think we’d find that recursion is harder for most folks than iteration.

The Java Program

Moving right along … let’s look at my Java program and see about making it actually work. I’ve added Pit’s two tests to the list:

   @Test public void opens() throws Exception {
        assertEquals(60, game.score(new Integer[] 
          {3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3}));
    }

    @Test public void spare() throws Exception {
        assertEquals(22, game.score(new Integer[] 
          {6,4,5,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}));
    }

    @Test public void perfect() throws Exception {
        assertEquals(300, game.score(new Integer[] 
          {10,10,10,10,10,10,10,10,10,10,10,10}));
    }

    @Test public void alternatingStrikeSpare() throws Exception {
        assertEquals(200, game.score(new Integer[] 
          { 10,5,5, 10,5,5, 10,5,5, 10,5,5, 10,5,5, 10}));
    }

    @Test public void alternatingSpareStrike() throws Exception {
        assertEquals(200, game.score(new Integer[] 
          { 5,5, 10,5,5, 10,5,5, 10,5,5, 10,5,5, 10,5,5}));
    }

    @Test public void trailingSpare() throws Exception {
        assertEquals(20, game.score(new Integer[] 
          { 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 10,5,5}));
    }

    @Test public void pitStrikeFinalFrame() throws Exception {
        assertEquals(15, game.score(new Integer[] 
          { 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 10,2,3}));
    }

    @Test public void pitStrikeNinthFrame() throws Exception {
        assertEquals(20, game.score(new Integer[] 
          { 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 10, 2,3}));
    }

The final test fails in my version, as it does in the Haskell and Ruby versions as well. (But not in Tom’s or Alistair’s, mind you.) Let’s see about fixing up the Java code. I’m also interested in refactoring it to address Anthony’s concern about the object eating its list instead of recurring on it.

Here’s the main loop, presently failing the last test:

   private Integer score() {
        if (rolls.size() == 0) return 0;
        if (rolls.size() == 3) return thisFrameScore();
        return thisFrameScore() + remainingScore();
    }

For no particular deep reason, just typing it in, I changed that to this:

   public Integer score(Integer[] rollsArray) {
        rolls = Arrays.asList(rollsArray);
        int score = 0;
        for (int frame = 0; frame < 10; frame++ ) {
            score += thisFrameScore();
            setRemainingRolls();
        }
        return score;
    }

The reasoning was that there are ten frames, and that I’d just use the existing functions, thisFrameScore() and setRemainingRolls(), ten times. It’s not a refactoring … the program didn’t work before I made these changes, and now it does. So it’s not a simple transformation, it’s a re-implementation. And the tests now run.

Many of my procedural implementations have used an index into the rolls list, rather than consuming it. That could address Anthony’s concern about using the list that way. As things are written right now, I’d need to pass the index around everywhere, which would be just as “bad” as passing the rolls.

Either way, it seems to me that either we need a new object that contains the rolls remaining to be scored, or we need to pass sublists of the current list as parameters to all the methods who look at pins. Which is all of them. Here’s the code as it stands right now:

public class BowlingGame {
    List<Integer> rolls;

    public Integer score(Integer[] rollsArray) {
        rolls = Arrays.asList(rollsArray);
        int score = 0;
        for (int frame = 0; frame < 10; frame++ ) {
            score += thisFrameScore();
            setRemainingRolls();
        }
        return score;
    }

    private Integer score() {
        if (rolls.size() == 0) return 0;
        if (rolls.size() == 3) return thisFrameScore();
        return thisFrameScore() + remainingScore();
    }

    private Integer remainingScore() {
        setRemainingRolls();
        return score();
    }

    private Integer thisFrameScore() {
        Integer frameScore = 0;
        for (Integer roll : thisFramesRolls()) 
            frameScore += roll;
        return frameScore;
    }

    private List<Integer> thisFramesRolls() {
        return rolls.subList(0, numberOfRollsToScore());
    }

    private int numberOfRollsToScore() {
        return (isMark()) ? 3: 2;
    }

    private boolean isMark() {
        return isStrike() || isSpare();
    }

    private boolean isStrike() {
        return rolls.get(0) == 10;
    }

    private boolean isSpare() {
        return rolls.get(0) + rolls.get(1) == 10;
    }

    private void setRemainingRolls() {
        rolls =  rolls.subList(frameSize(rolls), rolls.size());
    }

    private int frameSize(List<Integer> rolls) {
        return isStrike()? 1: 2;
    }
}

The score() method is no longer used: we could get rid of it. It’s not easy to see what to do beyond this, but I have an idea. Basically I need to start passing the rolls list rather than using it as a member variable, if I’m to work in the way Anthony prefers. I’m willing to try that, to see whether I like the result better. One way to do that will be to rename the rolls member variable, and then let the compiler tell me what to fix.

I did that, making these changes by rote. Note that I am using the newly-named rolls variable, rollsXXX, in a couple of places. We’ll fix that in a moment.

public class BowlingGame {
    List<Integer> rollsXXX;

    public Integer score(Integer[] rollsArray) {
        List<Integer> rolls = Arrays.asList(rollsArray);
        int score = 0;
        for (int frame = 0; frame < 10; frame++ ) {
            score += thisFrameScore(rolls);
            setRemainingRolls(rolls);
            rolls = rollsXXX;
        }
        return score;
    }

    private Integer thisFrameScore(List<Integer> rolls) {
        Integer frameScore = 0;
        for (Integer roll : thisFramesRolls(rolls)) 
            frameScore += roll;
        return frameScore;
    }

    private List<Integer> thisFramesRolls(List<Integer> rolls) {
        return rolls.subList(0, numberOfRollsToScore(rolls));
    }

    private int numberOfRollsToScore(List<Integer> rolls) {
        return (isMark(rolls)) ? 3: 2;
    }

    private boolean isMark(List<Integer> rolls) {
        return isStrike(rolls) || isSpare(rolls);
    }

    private boolean isStrike(List<Integer> rolls) {
        return rolls.get(0) == 10;
    }

    private boolean isSpare(List<Integer> rolls) {
        return rolls.get(0) + rolls.get(1) == 10;
    }

    private void setRemainingRolls(List<Integer> rolls) {
        rollsXXX =  rolls.subList(frameSize(rolls), rolls.size());
    }

    private int frameSize(List<Integer> rolls) {
        return isStrike(rolls)? 1: 2;
    }
}

The tests all run again. There’s that one hack with rollsXXX being used to pass the value around but that will be readily fixed by changing setRemainingRolls to getRemainingRolls.

Is there some easy way to give “List<Integer>” a better name? It looks really ugly with all that going on. I could build a specialized Rolls class, I suppose. There doesn’t seem to be a typedef … but I digress. First, let’s get rid of the set and the member variable:

   public Integer score(Integer[] rollsArray) {
        List<Integer> rolls = Arrays.asList(rollsArray);
        int score = 0;
        for (int frame = 0; frame < 10; frame++ ) {
            score += thisFrameScore(rolls);
            rolls = getRemainingRolls(rolls);
        }
        return score;
    }

with
    private List<Integer> getRemainingRolls(List<Integer> rolls) {
        return rolls.subList(frameSize(rolls), rolls.size());
    }

Tests are green, and rollsXXX is removed. Now what’s not to like? Well, rolls is still being used as a variable being counted down. We might prefer to get rid of that notion altogether. Let’s extract a score() method that uses the list as a parameter:

   public Integer score(Integer[] rollsArray) {
        List<Integer> rolls = Arrays.asList(rollsArray);
        return score(rolls);
    }

    private Integer score(List<Integer> rolls) {
        int score = 0;
        for (int frame = 0; frame < 10; frame++ ) {
            score += thisFrameScore(rolls);
            rolls = getRemainingRolls(rolls);
        }
        return score;
    }

We’ll inline that temp back in, while we’re thinking of it:

   public Integer score(Integer[] rollsArray) {
        return score(Arrays.asList(rollsArray));
    }

Well … where are we? We’ve removed the objection about the rolls member variable counting down, but we have just converted it to a temp which is counted down. It seems that the only way to get rid of the assignment is to do some kind of recursive call, either recurring into our new score() method, or creating a new object, as Anthony did. But given the bug Pit found, neither of those is likely to work. I could imagine passing a declining frame count into the score() method. Let’s try that. It’s a big bite and I expect trouble:

   public Integer score(Integer[] rollsArray) {
        return score(Arrays.asList(rollsArray), 10);
    }

    private Integer score(List<Integer> rolls, int frameNumber) {
        if (frameNumber == 0) return 0;
        return thisFrameScore(rolls) + score(getRemainingRolls(rolls), frameNumber-1);
    }

Well, it wasn’t a big bite after all, but I still did get trouble, all due to typing frameNumber– instead of frameNumber-1. The result, of course, was that the recursion never ended until I tried to sublist an empty array, since I kept passing 10 into the recursion. Then, the program threw an array bounds exception. After I fixed that, it worked fine, and all the tests are passing.

However …

The transformation from the recursive version that didn’t work, to the loop version that did, was basically a rewrite, not a refactoring. It’s a small rewrite, but a rewrite nonetheless. Sometimes we have to do that, certainly, especially when the program isn’t working. But it felt like a big step to me, moving away from a recursive implementation to an iterative one. Then, at the end, moving back from iterative to recursive, while passing in a count variable, was again a bigger step than I like.

There are canned ways to convert some loops to recursions and back again. I remember learning about them when I was studying computer science lo! these many years ago. In the first case, I don’t think such an algorithm would have helped, since we were trying to move from broken to working. In the final case, I don’t know whether there was a formal transformation that would have helped or not. I can imagine some intermediate step through a frame-scoring function that was sensitive to the frame count, but it doesn’t seem helpful, especially since I was just converting six lines of code to two.

Today’s Summary

There has been more trouble in this sequence of implementations than we usually see. I attribute that trouble to inherently higher complexity in recursive solutions than iterative ones, though some readers do not agree. One way or another, something went not so smoothly, and the experience, while it wouldn’t cause me not to try a recursive solution, would certainly cause me to operate more carefully when working with this kind of thing. I would be inclined to use more tests — especially more tests that offer variation at the end of the rolls list. Other forms of care are probably needed … perhaps some work on paper or the like.

So far, though rumors of a version that use a fake frame as a stop marker are out there, we’ve not seen running tested code that uses that approach. Perhaps a reader will provide one, or perhaps I’ll play with that another day. For now … it’s time to wait for another round of comments, which are, as always, solicited.

Late Note …

Anthony writes that framesRemaining is a better name than frameNumber in my code above. He’s right. The code below reflects that change.

The Code

Here are the tests and code as they now stand:

package haskellBowling;

import static org.junit.Assert.*;
import org.junit.Before;
import org.junit.Test;

public class BowlingGameTest {
    BowlingGame game;

    @Before public void setUp() throws Exception {
        game = new BowlingGame();
    }

    @Test public void hookup() {
        assertTrue(true);
    }

    @Test public void opens() throws Exception {
        assertEquals(60, game.score(new Integer[] 
          {3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3}));
    }

    @Test public void spare() throws Exception {
        assertEquals(22, game.score(new Integer[] 
          {6,4,5,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}));
    }

    @Test public void perfect() throws Exception {
        assertEquals(300, game.score(new Integer[] 
          {10,10,10,10,10,10,10,10,10,10,10,10}));
    }

    @Test public void alternatingStrikeSpare() throws Exception {
        assertEquals(200, game.score(new Integer[] 
          { 10,5,5, 10,5,5, 10,5,5, 10,5,5, 10,5,5, 10}));
    }

    @Test public void alternatingSpareStrike() throws Exception {
        assertEquals(200, game.score(new Integer[] 
          { 5,5, 10,5,5, 10,5,5, 10,5,5, 10,5,5, 10,5,5}));
    }

    @Test public void trailingSpare() throws Exception {
        assertEquals(20, game.score(new Integer[] 
          { 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 10,5,5}));
    }

    @Test public void pitStrikeFinalFrame() throws Exception {
        assertEquals(15, game.score(new Integer[] 
          { 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 10,2,3}));
    }

    @Test public void pitStrikeNinthFrame() throws Exception {
        assertEquals(20, game.score(new Integer[] 
          { 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 0,0, 10, 2,3}));
    }
}

package haskellBowling;

import java.util.Arrays;
import java.util.List;

public class BowlingGame {

    public Integer score(Integer[] rollsArray) {
        return score(Arrays.asList(rollsArray), 10);
    }

    private Integer score(List<Integer> rolls, int framesRemaining) {
        if (framesRemaining == 0) return 0;
        return thisFrameScore(rolls) + score(getRemainingRolls(rolls), framesRemaining-1);
    }

    private Integer thisFrameScore(List<Integer> rolls) {
        Integer frameScore = 0;
        for (Integer roll : thisFramesRolls(rolls)) 
            frameScore += roll;
        return frameScore;
    }

    private List<Integer> thisFramesRolls(List<Integer> rolls) {
        return rolls.subList(0, numberOfRollsToScore(rolls));
    }

    private int numberOfRollsToScore(List<Integer> rolls) {
        return (isMark(rolls)) ? 3: 2;
    }

    private boolean isMark(List<Integer> rolls) {
        return isStrike(rolls) || isSpare(rolls);
    }

    private boolean isStrike(List<Integer> rolls) {
        return rolls.get(0) == 10;
    }

    private boolean isSpare(List<Integer> rolls) {
        return rolls.get(0) + rolls.get(1) == 10;
    }

    private List<Integer> getRemainingRolls(List<Integer> rolls) {
        return rolls.subList(frameSize(rolls), rolls.size());
    }

    private int frameSize(List<Integer> rolls) {
        return isStrike(rolls)? 1: 2;
    }
}

Posted on:

Written by: Ron Jeffries

Categorization: Articles

Recent Articles

XProgNew – Working with layout

I’ve been trying to learn some things about how the new implementation will handle the front page. The front page has a top row the most recent articles in two categories, “Beyond Agile” and “The Annals of Kate Oneal”, and …