In this essay, we’re going to look at a game called Ayoayo. As we’ll read, Ayoayo is part of the Mancala family of games that has spread throughout Africa, and beyond. We’ll write some code that would be useful if we were implementing an Ayoayo game, and along the way, we’ll look at how we can keep our functions decoupled from each other and themselves with dependency injection.

We’ll then look at how our gratuitous use of linear recursion also helps us keep our code decoupled, and teaches us how to write decoupled code even if we decided to use iteration.

But first, some personal recollections. Feel free to skip it if you want to dive right into code.

I believe this is a picture of my sister and me visiting a fort used to house slaves before their transportation (what a bloodless word) to the Americas, probably in Ghana.

Prelude: A Boy and a Game

africa 1968 – 1971

In 1968 or thereabouts, my mother took my sister and I on a trip to West Africa. We returned to Nigeria a year or so later, and lived there while she developed software for a brand-new IBM 360 that had been installed at the University of Ibadan.

It is difficult for me to explain the magnitude of the culture shock I experienced in Africa. In the 1960s, Toronto was much less visibly multicultural than it is today. I do not recall ever seeing a black police officer, teacher, or newscaster on television. In 1963, my great-uncle Leonard had become the first black MPP in Canada, but in 1968 he was still more of an exception than a minority.

And then I visited Africa. Almost everyone was black, where in Canada, almost everyone was white. I distinctly recall being amazed to visit the flight deck of our Air Afrique flight, and the black pilots let me sit in the co-pilot’s chair. The flight attendants were black as well, and everyone spoke French. I had never encountered such a thing.

In Africa, there was fantastic wealth, and there was wretched poverty as I’d never imagined. Many institutions in Africa were older than the country of Canada. That’s something you find in most of the old world, like England or Europe, but it was particularly stunning for me to look at things like the Great Mosque of Djenné. The first mosque on that site was built in the late 13th century, three centuries before the first Europeans set permanent foot in Canada.

In 1970, we were even in the crowds for the coronation procession of Opoku Ware II, 15th Emperor-King of the Ashanti people. The Empire of Ashanti was formed in 1701, a century and a half before Canada became a country. My brain exploded when we touched down in Africa, and continued to erupt the entire time we were there. Everything I encountered was literally fantastic.

From an early age, my mother had taken our education “in hand,” as they used to say. I was already aware of various important stories and facts about black people like Harriet Tubman. I think I had already read some Anansi stories from books she had imported by mail. You wouldn’t find things like that in a bookstore in those days.

And amongst all those great things, she may have also introduced me to some form of the game Oware in Toronto, but my recollection is that I first encountered it in Africa.

This board can be used to play many different kinds of Oware, including Ayoayo.

oware and ayoayo

What is Oware? Wikipedia puts it succinctly and well: Oware is an abstract strategy game among the Mancala family of board games (pit and pebble games) played worldwide with slight variations as to the layout of the game, number of players and strategy of play. Its origin is uncertain, but it is widely believed to be of Ashanti origin.

The games in the Mancala family have spread all over the world. They crossed the Sahara with the gold and salt trade to East Africa, where they then crossed to Southern Asia. I recall a friend visiting my house, who spotted a board and told me that she had played the game as a young girl in Malaysia.

One of its charms is its radical simplicity. It is often played with pebbles and its scooped out of the ground or sand. It can be played with cups and marbles, pennies, or even twiddly-winks. In that respect, it reminds me of tic-tac-toe. It can be played almost anywhere, almost any time, by almost everyone.

I think that I first learned to play Oware in Nigeria, because what I recall of the rules closely matches the rules of Ayoayo, the variation of the game played by the Yoruba people of Nigeria.

One of Ayoayo’s charms is its radical simplicity. It is often played with pebbles and its scooped out of the ground or sand.

how I learnt ayoayo is played

In Nigeria, bored children would play Ayoayo the way children play tic-tac-toe in the West. If there was a board handy, we’d play on that. If not, we could collect pebbles or coins and set up a makeshift board on paper or even the ground. But it was usually a board, as I recall. Every house had one, often several. Some houses would have a ceremonial board, an older, elaborate hand-carved board, elevated so that two people sitting on stools could play without the need of a table between them.

Ayoayo is played on the most common Oware layout, a board with two rows of six pits. Many boards also provide with a pit on each side of the board for “captured” stones, but this is optional when playing Ayoayo.

The players face each other with the board between them, such that each player has a row of six pits in front of them. These pits “belong” to that player. If extra pits are provided for captured stones, each player takes one for themselves, but the extra pits are not in play. (In some other games in the same family, pits for captured stones are used in play.)

We’ve mentioned capturing stones several times, and for good reason: The game play consists of capturing stones, and when the game is completed, the player who has captured the most stones, wins.

The rules are simple:

The game begins with four stones in each of the twelve pits. Thus, the game requires 48 stones. Pebbles, marbles, or even lego pieces can be used to represent the stones. A wooden board is nice, but pits can be scooped out of earth or sand to make a board. This extreme simplicity is part of the game’s charm, much as tic-tac-toe’s popularity stems in part from the fact that you can play a game with little more than a stick and a piece of flat earth.

The players alternate turns, as in many games.

On a player’s turn, they select one of their pits to “sow.” There are some exceptions listed below, but in general if the player has more than one pit with stones, they may select which one to sow. There are many variations on rules for how to sow the stones amongst the Mancala family of games, but in Ayoayo, sowing works like this:

• The player scoops all of the stones from the starting pit into their hand.
• Moving counter-clockwise, the player drops one stone into each pit.
• On their row, they move from left to right.
• If they reach the end of their row, they move from right to left on their opponent’s row (thus “counter-clockwise”).
• They always skip the starting pit on their row.
• The sowing pauses when they have sowed the last stone in their hand.

If the last stone lands in a pit on either side of the board that contains one or more stones, they scoop the stones up (including that last stone), and continue sowing. They continue to skip their original starting pit only, but can sow into any pits that get scooped up in this manner. This is called relay sowing.

If the last stone lands in an empty pit on that player’s own side, the player “captures” any stones that are in the pit on the opponent’s side of the board from their last pit.

If a player has no move on their turn, the game ends, and their opponent captures any remaining stones (which will–of course–be on their side).

If a player ends his or her turn with no seeds left in his or her row, the opponent must (if it is possible) choose his move in such a way to bring one or more seeds into the other’s row. If a player has several such moves (as is usually the case), the player may choose which move to make.

I learned those rules very quickly, and it was pretty easy to knock of game after game while laughing and joking with school mates or friends from the neighbourhood. Good times.

An Altair 8800 on display at the Smithsonian Institute

segue to implementing ayoayo

At that time in my life, I knew about computers, but I didn’t have proper access to a computer. I couldn’t write COBOL or FORTRAN programs and run them on the computer at the University. Nobody had a home computer: The [Altair 8800] hadn’t been invented yet, and I had never heard of Douglas Engelbart, much less seen The Mother of All Demos.

If I had, I doubtless would have tried to write a program to play Ayoayo with me. But that was then. How about now? What would be involved in writing a program to play Ayoayo? Let’s explore implementing some of the rules. We won’t build a complete game, but we will explore some ideas around decoupling and recursion as we go.

A natural Mancala game.

Implementing Ayoayo

a starting point: the board, the stones, and sowing

If we were going to make an Ayoayo program, where would we start?

Let’s start with a simple idea: We’ll have to represent the state of the game. We could use an array for the twelve pits of the game, with an integer representing the number of stones in that pit. We’ll initialize it with four stones in each pit:

const gamePits = Array(12).fill(4);

Associating the elements of the array with the pits belonging to the players.

In Ayoayo, a full turn involves relay sowing as described above:

When relay sowing, if the last stone during sowing lands in an occupied hole, all the contents of that hole, including the last sown stone, are immediately re-sown from the hole.

The other kind of sowing, as used in other games from the same family, is just called sowing. The sowing stops when the last stone is sown, regardless of whether the last stone lands in an occupied or unoccupied pit.

It’s fairly obvious that if we make a function for sowing, we can use that to make a function for relay sowing, so let’s start with an ordinary sowing function. We’ll make a relay sowing function later.

The first thing we need is a function to scoop up the stones from a pit:

function scoop(fromPit) {
  const stonesInHand = gamePits[fromPit];

  gamePits[fromPit] = 0;

  return stonesInHand;
}

We’ll also need a function to distribute stones. It needs to know which pit to skip, where to start distributing, and how many stones to are in the hand that need to be distributed:

function distribute(skipPit, currentPit, stonesInHand) {

  // now what?

}

The first thing our distribute function needs to do is place a stone from the hand into the current pit. With a wrinkle that if the current pit is the skip pit, move to the next pit:

function nextPit(pit) {
  return (pit + 1) % 12;
}

function distribute(skipPit, currentPit, stonesInHand) {

  if (currentPit === skipPit) {
    currentPit = nextPit(currentPit);
  }

  ++gamePits[currentPit];
  --stonesInHand;

  // And now what?
}

What should we do next?

Well, if we don’t have any more stones in hand, we’re done. We should return the current pit so that other code can do things like work out whether to continue sowing, or determine whether to capture any stones from our opponent:

function nextPit(pit) {
  return (pit + 1) % 12;
}

function distribute(skipPit, currentPit, stonesInHand) {

  if (currentPit === skipPit) {
    currentPit = nextPit(currentPit);
  }

  ++gamePits[currentPit];
  --stonesInHand;

  if (stonesInHand === 0) {
    return currentPit;
  } else if (stonesInHand > 0) {
    // what goes here?
  }
}

If we still have stones, then what? We need to keep sowing. We could rewrite distribute to have a loop of so kind, maybe do { ... } while (...). But hang on!

distribute is a function that takes a pit to skip, a current pit, and a number of stones in hand. It returns the result of sowing stones. That’s what we need to return, with just one alteration: We need distribute starting with the next pit. So let’s just do that:

function nextPit(pit) {
  return (pit + 1) % 12;
}

function distribute(skipPit, currentPit, stonesInHand) {

  if (currentPit === skipPit) {
    currentPit = nextPit(currentPit);
  }

  ++gamePits[currentPit];
  --stonesInHand;

  if (stonesInHand === 0) {
    return currentPit;
  } else if (stonesInHand > 0) {
    return distribute(skipPit, nextPit(currentPit), stonesInHand);
  }
}

With scoop and distribute, we can write sow:

function sow(skipPit, fromPit = skipPit) {
  return distribute(skipPit, nextPit(fromPit), scoop(fromPit));
}

Let’s try it:

sow(0)
  //=> 4

gamePits
  //=> [0, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4]

We can test it by hand.

And after sowing once, it looks like this:

Now, there were five stones in the last pit (pit 4). If there are two or more stones in the last pit, it wasn’t empty before we sowed the last stone into it. So when relay sowing, we’d sow again, only this time we’ll tell our function start at pit 4, where we left off last time:

sow(0, 4)
  //=> 9

Five stones in the last pit (9), Let’s do it again:

sow(0, 9)
  //=> 3

Six stones in pit 3! Again:

sow(0, 3)
  //=> 9

pits
  //=> [0, 6, 6, 0, 1, 6, 6, 6, 6, 1, 5, 5]

Aha, just one stone in pit 9, we’re done. Let’s try it by hand, remembering to skip pit 0, and compare:

Let’s look at our accumulated code all together:

function scoop(fromPit) {
  const stonesInHand = gamePits[fromPit];

  gamePits[fromPit] = 0;

  return stonesInHand;
}

function nextPit(pit) {
  return (pit + 1) % 12;
}

function distribute(skipPit, currentPit, stonesInHand) {

  if (currentPit === skipPit) {
    currentPit = nextPit(currentPit);
  }

  ++gamePits[currentPit];
  --stonesInHand;

  if (stonesInHand === 0) {
    return currentPit;
  } else if (stonesInHand > 0) {
    return distribute(skipPit, nextPit(currentPit), stonesInHand);
  }
}

function sow(skipPit, fromPit = skipPit) {
  return distribute(skipPit, nextPit(fromPit), scoop(fromPit));
}

let gamePits = Array(12).fill(4);

sow(0)
  //=> 4
sow(0, 4)
  //=> 9
sow(0, 9)
  //=> 3
sow(0, 3)
  //=> 9

gamePits
  //=> [0, 6, 6, 0, 1, 6, 6, 6, 6, 1, 5, 5]

We’re off to a reasonable start. And as it happens, the recursive solution is actually straightforward to explain and to implement.

Toguz korgool (Kyrgyz: тогуз коргоол - “nine sheep droppings”) or toguz kumalak/toghiz qumalaq (Kazakh: тоғыз құмалақ), is a two-player game in the mancala family that is played in Central Asia.

a most practical digression

Let’s look at our calls to sow again:

sow(0)
sow(0, 4)
sow(0, 9)
sow(0, 3)

Shall we try it again?

sow(0)
  //=> undefined

D’oh! We forgot to reset the board. Our sow function relies upon a mutable value from outside of its body–gamePits–and indeed it mutates that value by changing the contents of the array. Thus, when you invoke sow, you don’t know what you’re going to get unless you already know the state of gamePits.

We say that sow is coupled to gamePits. In order to test sow, we have to first carefully set up gamePits to align with our expectations. We see this kind of thing when writing production code for large systems: Many tests do more work setting up and tearing down all of the required initial conditions than they do actually testing functions and methods.

So coupling a function to a mutable value requires us to keep track of that value in order to understand what sow will or won’t do. That adds some complexity to understanding our system. And this coupling is transitive: Not only is sow coupled to gamePits, any other function we write that is coupled to gamePits, becomes coupled to sow. Running sow changes the behaviour of any function coupled to gamePits because sow mutates gamePits.

In fact, sow is coupled to itself! Even if we remember to correctly initialize gamePits before running sow, the order in which we invoke sow affects the results.

Having a single variable, gamePits, describing the state of the game in progress does feel intuitively sound. There is only one board in the game, and when we sow stones, we change it. So why shouldn’t we “model the real world accurately?”

That question is easy to answer: I used to own a typewriter. It had no “undo.” It had no “copy” or “paste,” those functions were accomplished by making copies of pages and laboriously cutting sections of text out with an x-acto blade and gluing them onto other pieces of paper. The text editor I am using now is superior to my typewriter precisely because it does not insist on modelling the real world accurately.

Modelling the real world is a tool for exploring ideas in software and for helping others read our software: What is familiar, subjectively feels “intuitive.”¹ But when the modelling interferes with our ability to understand our software’s behaviour, we should relax our desire to make everything about modelling. What we seek is maximum understandability and maximum flexibility, not maximum fidelity.

So how can we “decouple” or code from itself and each other?

Picture of a train coupling.

decoupling code from shared mutable values

The easiest thing is the obvious thing: If a function shares mutable values with another function (or itself!), and we wish to remove the coupling caused by changes to the shared mutable values, we rewrite the functions to get rid of the shared mutable values. This is an easy refactoring:²

• We take all of the references to shared mutable values that functions must read, and replace them with parameters.
• We take all of the references to shared mutable values that functions must write, and replace them with creating copies of the shared mutable values. We then return those copies along with any other return values the functions already have.

So our code becomes:

function scoop(before, fromPit) {
  const after = before.slice(0);
  const stonesInHand = after[fromPit];

  after[fromPit] = 0;

  return [after, stonesInHand];
}

function nextPit(pit) {
  return (pit + 1) % 12;
}

function distribute(before, skipPit, currentPit, stonesInHand) {
  const after = before.slice(0);

  if (currentPit === skipPit) {
    currentPit = nextPit(currentPit);
  }

  ++after[currentPit];
  --stonesInHand;

  if (stonesInHand === 0) {
    return [after, currentPit];
  } else if (stonesInHand > 0) {
    return distribute(after, skipPit, nextPit(currentPit), stonesInHand);
  }
}

function sow(before, skipPit, fromPit = skipPit) {
  const [after, pitsInHand] = scoop(before, fromPit);

  return distribute(after, skipPit, nextPit(fromPit), pitsInHand);
}

And we use it like this:

let gamePits = Array(12).fill(4);

sow(gamePits, 0)
  //=> [
         [0, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4],
         4
       ]

If we want to update the game mutable values, we can choose to do that:

let gamePits = Array(12).fill(4);
let lastPit;

[gamePits, lastPit] = sow(gamePits, 0);

gamePits
  //=> [0, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4]

At first sight, there seem to be more moving parts with this approach.

But in truth, they were always there, it’s just that we “lifted” them into the interface of the scoop, distribute, and sow functions where we can see them. And now, we can test any arbitrary invocation without having to remember to set things up in advance.³

For example, here’s the second call we made:

sow([0, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4], 0, 4)
  //=> [
         [0, 5, 5, 5, 0, 5, 5, 5, 5, 5, 4, 4],
         9
       ]

Checks out, and so do the third and fourth calls we made:

sow([0, 5, 5, 5, 0, 5, 5, 5, 5, 5, 4, 4], 0, 9)
  //=> [
         [0, 6, 6, 6, 0, 5, 5, 5, 5, 0, 5, 5],
         3
       ]

sow([0, 6, 6, 6, 0, 5, 5, 5, 5, 0, 5, 5], 0, 3)
  //=> [
         [0, 6, 6, 0, 1, 6, 6, 6, 6, 1, 5, 5],
         9
       ]

We get to the same place, but we can run our “tests” in any order and don’t have to do any set up in advance.

The lesson learned is that decoupling functions from mutable mutable values makes them easier to understand and test. And if we want to model the “real world” by having a value representing the current game mutable values, we can still do that:

let gamePits = Array(12).fill(4);

let initialChoice = 0;
let lastPit;

[gamePits, lastPit] = sow(gamePits, initialChoice);
[gamePits, lastPit] = sow(gamePits, initialChoice, lastPit);
[gamePits, lastPit] = sow(gamePits, initialChoice, lastPit);
[gamePits, lastPit] = sow(gamePits, initialChoice, lastPit);

gamePits[lastPit]
  //=> 1

gamePits
  //=> [0, 6, 6, 0, 1, 6, 6, 6, 6, 1, 5, 5]

We’re now ready to automate the “relay sowing.”

Relayer is an album by Prog Rock progenitors Yes. It is notable for being the first album they recorded without Rick Wakeman, who wanted to break from the emphasis on long-form compositions.

relay sowing

We have implemented “relay sowing” by hand above. It’s time to write a relaySow function. We could modify sow, but accreting new functionality on top of old is a recipe for bloat.

How do we start relaySow? Well, with sow:

function relaySow(before, skipPit, currentPit = skipPit) {
  let [after, lastPit] = sow(before, skipPit, currentPit);

  // what happens next?
}

Well, what does happen next? I think we know the answer: We need to check and see whether the number of stones in the last pit is one or not:

function relaySow(before, skipPit, currentPit = skipPit) {
  let [after, lastPit] = sow(before, skipPit, currentPit);

  if (after[lastPit] === 1) {
    return [after, lastPit];
  } else {
    // now what?
  }
}

“Now what,” indeed. Now what? We can’t just call sow again and return the result, that won’t work if we end up needing to sow a third time. We’d need all sorts of nested if statements. Yecch.

We could rewrite relaySow to have a loop of so kind, maybe do { ... } while (...). But hang on! With distribute, we recursively called distribute when there was more work to be done. Let’s use the same pattern:

function relaySow(before, skipPit, currentPit = skipPit) {
  let [after, lastPit] = sow(before, skipPit, currentPit);

  if (after[lastPit] === 1) {
    return [after, lastPit];
  } else {
    return relaySow(after, skipPit, lastPit);
  }
}

let gamePits = Array(12).fill(4);
let lastPit;

[gamePits, lastPit] = relaySow(gamePits, 0);

lastPit
  //=> 9

gamePits
  //=> [0, 6, 6, 0, 1, 6, 6, 6, 6, 1, 5, 5]

We have relay sowing working. What else do we need to model a player’s turn?

Go is a completely different game from the Mancala family, but they share the notion of capturing stones.

capturing stones

Relay sowing ends when the last stone is placed in an empty hole. In Ayoayo, if that empty hole is on the player’s side, they capture all of the stones in the corresponding hole on the opponent’s side:

function capturedStones(before, startPit, endPit) {
  const endedOnThePlayersSide = startPit < 6 === endPit < 6;

  if (endedOnThePlayersSide) {
    const pitOnOpponentsSide = 11 - endPit;
    const after = before.slice(0);
    const stones = after[pitOnOpponentsSide];

    after[pitOnOpponentsSide] = 0;

    return [after, stones];
  } else {
    return [before, 0];
  }
}

We will try it:

const gameStart = Array(12).fill(4);
const startPit = 0;

const [afterSowing, endPit] = relaySow(gameStart, startPit);
const [afterTurn, captured] = capturedStones(afterSowing, startPit, endPit);

afterTurn
  //=> [0, 6, 6, 0, 1, 6, 6, 6, 6, 1, 5, 5]

endPit
  //=> 9

captured
  //=> 0

No stones were captured, because the last pit was pit nine on the other side. How can we get a test case that captures stones? Should we try the numbers at random or in sequence? We don’t have to. The starting position of the board is symmetrical under rotation. So if move 0 ends up with the board in a certain layout after sowing, and ending on pit 9, it follows that choosing 1 should lead to exactly the same layout, but rotated one pit counter-clockwise, and the last pit will be 10.

Well this makes things easy. If the player chooses to start with 3, the last pit should be 0, on the player’s own side:

const gameStart = Array(12).fill(4);
const startPit = 3;

const [afterSowing, endPit] = relaySow(gameStart, startPit);
const [afterTurn, captured] = capturedStones(afterSowing, startPit, endPit);

afterSowing
  //=> [1, 5, 5, 0, 6, 6, 0, 1, 6, 6, 6, 6]

afterTurn
  //=> [1, 5, 5, 0, 6, 6, 0, 1, 6, 6, 6, 0]

endPit
  //=> 0

captured
  //=> 6

The state of the board after the first player chooses pit three.

If we want to update the game state, we’ll need a notion of a “score,” and we can change capturedStones into handleCapture:

function ownerOf(pit) {
  return pit > 5 ? 1 : 0
}

function handleCaptures(beforeBoard, beforeScore, startPit, endPit) {
  const endedOnThePlayersSide = startPit < 6 === endPit < 6;

  if (endedOnThePlayersSide) {
    const pitOnOpponentsSide = 11 - endPit;
    const afterBoard = beforeBoard.slice(0);
    const playerNumber = ownerOf(startPit);
    const afterScore = Object.assign(
      beforeScore,
      { [playerNumber]: beforeScore[playerNumber] + beforeBoard[pitOnOpponentsSide] }
    );
    afterBoard[pitOnOpponentsSide] = 0;

    return [afterBoard, afterScore];
  } else {
    return [beforeBoard, beforeScore];
  }
}

const gameStart = Array(12).fill(4);
const scoreStart = { 0: 0, 1: 0 };
const startPit = 3;

const [afterSowing, endPit] = relaySow(gameStart, startPit);
const [afterTurn, scoreAfter] = handleCaptures(afterSowing, scoreStart, startPit, endPit);

afterTurn
  //=> [1, 5, 5, 0, 6, 6, 0, 1, 6, 6, 6, 0]

scoreAfter
  //=> {0: 6, 1: 0}

Finally, we can assemble sowing and capturing together:

function sowAndCapture(beforeBoard, beforeScore, startPit) {
  const [afterSowing, endPit] = relaySow(beforeBoard, startPit);
  const [afterTurn, scoreAfter] = handleCaptures(afterSowing, beforeScore, startPit, endPit);

  return [afterTurn, scoreAfter];
}

const gameStart = Array(12).fill(4);
const scoreStart = { 0: 0, 1: 0 };
const startPit = 3;

const [afterTurn, scoreAfter] = sowAndCapture(gameStart, scoreStart, startPit);

afterTurn
  //=> [1, 5, 5, 0, 6, 6, 0, 1, 6, 6, 6, 0]

scoreAfter
  //=> {0: 6, 1: 0}

We now have almost everything we need to referee a game between two players. Not enough to write a program to play on its own, but we almost have enough to get going on—for example—a web site that would allow players to play each other online. So what are we missing?

Two things: Determining when the game is over, and determining which moves are permissible. The former depends upon the latter, so our next step is to determine which moves a player is allowed to make.

In Ayoayo, some moves are permitted, and some are prohibited.

permissible moves

In working out which moves are permissible, we need think of only three rules. First, a player can only choose one of the six pits on their side. We’ll call this the set of potential moves. Second, a player can only choose a potential move if that pit has one or more stones in it. We’ll call the set of potential moves that also have stones to be the set of possible moves:

function pitsBelongingTo(player) {
  if (player === 0) {
    return [0, 1, 2, 3, 4, 5];
  } else {
    return [6, 7, 8, 9, 10, 11];
  }
}

Now what about filtering the potential moves down to those that are possible?

function possible(pits, pit) {
  return pits[pit] > 0;
}

function possibleMoves(pits, moves) {
  if (moves.length === 0) {
    return moves
  } else {
    const [first, ...rest] = moves;

    if (possible(pits, first)) {
      return [first].concat(possibleMoves(pits, rest));
    } else {
      return possibleMoves(pits, rest);
    }
  }
}

We can see this in action from our previous work:

const gameStart = Array(12).fill(4);
const scoreStart = { 0: 0, 1: 0 };
const startPit = 3;

const [afterSowing, endPit] = relaySow(gameStart, startPit);
const [afterTurn, scoreAfter] = handleCaptures(afterSowing, scoreStart, startPit, endPit);
const potentialMovesForPlayerOne = pitsBelongingTo(1);
const possibleMovesForPlayerOne = possibleMoves(afterTurn, potentialMovesForPlayerOne);

afterTurn
  //=> [1, 5, 5, 0, 6, 6, 0, 1, 6, 6, 6, 0]

possibleMovesForPlayerOne
  //=> [7, 8, 9, 10]

We’ve covered rules one and two. Now how about rule three?

Three buffalo. Aren’t they magnificent?

implementing the third rule, with a digression into optimization

The third rule for whether a move is permissible is far more interesting than the first two:

If a player ends his or her turn with no seeds left in his or her row, the opponent must (if it is possible) choose his move in such a way to bring one or more seeds into the other’s row. This scheme is found in many Mancala games, and sometimes referred to as “feeding” the opponent (i.e., save the opponent from starving).

As expressed, this rule is not equivalent to the simpler, “If you can make a move that leaves your opponent with a move, you must.” This rule only applies to the situation where the opponent’s play leaves them with no stones/seeds on their row. Fine, let’s code that.

The first and obvious thing to take into account is that this has no effect if the opponent has one or more pits with stones in them. For that, we’ll need a function to determine whether a player has at least one possible move. We’ll use the [first, ...rest] recursive pattern from above.

After all, a player has at least one possible move out of some set of moves if the first move is possible or if there is at least one possible move out of the remaining moves, right? Here’s our first crack at it. atLeastOnePossibleMove works out which row belongs to a particular player, and then calls atLeastOne, which is recursive in much the same way that possibleMoves was recursive, breaking the list of possible moves down into first and ...rest as it goes:

function atLeastOne(pits, moves) {
  if (moves.length === 0) {
    return false;
  } else {
    const [first, ...rest] = moves;

    return pits[first] > 0 || atLeastOne(pits, rest);
  }
}

function atLeastOnePossibleMove(pits, player) {
  const moves = pitsBelongingTo(player);

  return atLeastOne(pits, moves);
}

Since we’re already familiar with how this works, we can take a moment and consider some of the ways it could be better.

One of the issues with [first, ...rest] = moves is that we’re not just getting the first element of the array, we’re also copying all the other elements of the array into rest. That’s insignificant for five elements, but as a pattern, it can get expensive if we start dealing with really big arrays. And since we do it for every element, we end up performing approximately n-squared over two copies.

That being said, our code is safe. Let’s say we rewrite atLeastOne to look like this:

function atLeastOne(pits, moves) {
  if (moves.length === 0) {
    return false;
  } else {
    const first = moves.pop();

    return pits[first] > 0 || atLeastOne(pits, moves);
  }
}

Now it destructively modifies moves. Which actually works, and gets rid of the copies! The reason it is fine is that every time pitsBelongingTo is called, it generates a new array for moves, so modifying that array doesn’t break the code.

But one day, somebody has an idea: Why are we making new arrays every time we call pitsBelongingTo? If they don’t look too closely at atLeastOne, they may think this is wasteful. So they write this optimization:

const PLAYER_TO_ROW = {
  0: [0, 1, 2, 3, 4, 5],
  1: [6, 7, 8, 9, 10, 11]
};

function pitsBelongingTo(player) {
  return PLAYER_TO_ROW[player];
}

Now atLeastOnePossibleMove doesn’t need to create a new array every time it’s called. And if we were using the old version of atLeastOne, it would work. But with our new code that modifies the array it is given, the arrays within PLAYER_TO_ROW get modified, and you can’t call atLeastOnePossibleMove more than once.

We now have two optimizations. Either one by themselves works, but if they’re both implemented together, our code is broken!

The general shape of this problem is a dependency between the two functions. We call this a “resource ownership” problem. Both functions think they “own” the array and are entitled to make assumptions about what they can do with it and what they can expect from other functions.

Some other languages have special types and other features to establish constraints, so that if a function expects to modify an array it is given, the compiler can detect whether a piece of code giving it an array expects that array to remain untouched.

In JavaScript, we have a couple of options. One is to Object.freeze() PLAYER_TO_ROW:

const PLAYER_TO_ROW = Object.freeze({
  0: Object.freeze([0, 1, 2, 3, 4, 5]),
  1: Object.freeze([6, 7, 8, 9, 10, 11])
});

function pitsBelongingTo(player) {
  return PLAYER_TO_ROW[player];
}

That prevents the situation where one piece of code thinks the array is immutable, and another tries to mutate it. JavaScript gives us an Unable to delete property. error. And frankly, this is an excellent practice whenever we have entities we think are immutable.

But although it doesn’t apply here, sometimes function A does want some object, O, to be mutable for its own purposes, but when it passes O to function B, it doesn’t expect B to mutate it. Object.freeze(O) is not helpful, A wants to mutate O itself, it just doesn’t want anybody else to mutate O.

What to do?

managing ownership of mutable data structures with encapsulation

Here’s one pattern that solves both scenarios.

First, we should look at a function like atLeastOne and think about its contract with other functions. It takes an array of moves as a parameter, and reports something else. Clearly, it is not being asked to change moves. That’s an implementation detail. But we want to copy arrays for performance purposes.

The solution in many cases is to copy the array, but only once. Something like this:

function atLeastOne(pits, moves) {
  const disposableMoves = moves.slice(0);

  return recursiveAtLeastOne(pits, disposableMoves);
}

function recursiveAtLeastOne(pits, disposableMoves) {
  if (disposableMoves.length === 0) {
    return false;
  } else {
    const first = disposableMoves.pop();

    return pits[first] > 0 || recursiveAtLeastOne(pits, disposableMoves);
  }
}

Now we can call atLeastOne with an array and never worry about whether it will mutate the array, because it makes a copy and passes the copy to recursiveAtLeastOne.

But now we have a different problem. What if someone tries to invoke recursiveAtLeastOne. We’re relying on a naming convention to remind them not to trust it with an array. That’s no good. A better solution is to encapsulate recursiveAtLeastOne so that it isn’t available to any other function.

One way to do that is with an ES6 module. But a simpler way, good enough for our purposes, is to use function scope, like this:

function atLeastOne(pits, moves) {
  const disposableMoves = moves.slice(0);

  return recursiveAtLeastOne(pits, disposableMoves);

  function recursiveAtLeastOne(pits, disposableMoves) {
    if (disposableMoves.length === 0) {
      return false;
    } else {
      const first = disposableMoves.pop();

      return pits[first] > 0 || recursiveAtLeastOne(pits, disposableMoves);
    }
  }
}

By hiding recursiveAtLeastOne inside of atLeastOne, we prevent other functions from calling it. They can only call atLeastOne, which has the same behaviour as the original version–it doesn’t mutate the array passed in–but makes only one copy.

And if we have no use for atLeastOne other than atLeastOnePossibleMove calling it, we can nest it inside atLeastOnePossibleMove:

function atLeastOnePossibleMove(pits, player) {
  const moves = pitsBelongingTo(player);

  return atLeastOne(pits, moves);

  function atLeastOne(pits, moves) {
    const disposableMoves = moves.slice(0);

    return recursiveAtLeastOne(pits, disposableMoves);

    function recursiveAtLeastOne(pits, disposableMoves) {
      if (disposableMoves.length === 0) {
        return false;
      } else {
        const first = disposableMoves.pop();

        return pits[first] > 0 || recursiveAtLeastOne(pits, disposableMoves);
      }
    }
  }
}

This is beginning to look like a Turducken. If atLeastOnePossibleMove ends up owning atLeastOne, we don’t need to make it safe, so let’s revert to:

function atLeastOnePossibleMove(pits, player) {
  const disposableMoves = pitsBelongingTo(player).slice(0);

  return atLeastOne(pits, moves);

  function atLeastOne(pits, disposableMoves) {
    if (disposableMoves.length === 0) {
      return false;
    } else {
      const first = disposableMoves.pop();

      return pits[first] > 0 || atLeastOne(pits, disposableMoves);
    }
  }
}

The upside is that we do far less copying. The downside is that atLeastOne is no longer nicely decoupled from itself. But since it is now an implementation detail of atLeastOnePossibleMove, that probably doesn’t matter. This pattern comes up a fair bit: Start with the simplest code, and refactor to faster code when the profiler shows you that it matters.[^nope]

But this optimization is for illustration purposes only, there are far, far faster ways to write the code if performance is all that matters.⁴

What we’ve really learned is that when we have an implementation detail, we want to hide that detail from the rest of the code. That’s what encapsulation is all about, and we don’t always need objects, methods, or modules to do it: Sometimes a nested function is exactly the right tool for the encapsulation job.

returning to permissable moves

Now let’s move on and get started on permissibleFilter:

function permissibleFilter(pits, moves) {
  // the degenerate case
  if (moves.length === 0) {
    return moves;
  }

  const firstMove = moves[1];
  const otherPlayer = ownerOf(firstMove);
  const otherPlayerHasStones =
    atLeastOnePossibleMove(pits, otherPlayer);

  if (otherPlayerHasStones) {
    return moves;
  }

  // Ok, what do we do here?
}

We’ve handled the obvious: If the other player has stones on their side of the board, any of the supplied moves are permissible. But if they don’t have any stones on their side of the board, we have to figure out if any of the moves will “feed” them by placing at least one stone on their side of the board.

Sounds like we need another filter function:

function movesThatFeedTheOtherPlayer(before, moves) {
  // the degenerate case
  if (moves.length === 0) {
    return moves;
  }

  const [first, ...rest] = moves;
  const irrelevantScore = { 0: 0, 1: 0 };
  const [after] = sowAndCapture(before, irrelevantScore, first);
  const otherPlayer = otherPlayerFor(ownerOf(first));
  const otherPlayerHasStonesAfter =
    atLeastOnePossibleMove(after, otherPlayer);

  if (otherPlayerHasStonesAfter) {
    return [first].concat(movesThatFeedTheOtherPlayer(before, rest));
  } else {
    return movesThatFeedTheOtherPlayer(before, rest);
  }
}

const lateGameBoard = [1, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0];
const potentialMovesForPlayerZero = pitsBelongingTo(0);
const possibleMovesForPlayerZero = possibleMoves(lateGameBoard, potentialMovesForPlayerZero);
const movesThatFeedPlayerOne = movesThatFeedTheOtherPlayer(lateGameBoard, possibleMovesForPlayerZero);

movesThatFeedPlayerOne
  //=> [2]

And now we can finish permissibleFilter, then put it all together into permissibleMoves:

function permissibleFilter(pits, moves) {
  // the degenerate case
  if (moves.length === 0) {
    return moves;
  }

  const firstMove = moves[1];
  const otherPlayer = otherPlayerFor(ownerOf(firstMove));
  const otherPlayerHasStones =
    atLeastOnePossibleMove(pits, otherPlayer);

  if (otherPlayerHasStones) {
    return moves;
  } else {
    const permissibleMoves = movesThatFeedTheOtherPlayer(pits, moves);

    if (permissibleMoves.length > 0) {
      return permissibleMoves;
    } else {
      // slightly irrelevant, as the gamne is about to end
      // no matter which move is chosen
      return moves;
    }
  }
}

function permissibleMoves(before, player) {
  const potentialMovesForPlayer = pitsBelongingTo(player);
  const possibleMovesForPlayer = possibleMoves(lateGameBoard, potentialMovesForPlayer);
  const permissibleMovesForPlayer = permissibleFilter(lateGameBoard, possibleMovesForPlayer);

  return permissibleMovesForPlayer;
}

const lateGameBoard = [1, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0];

permissibleMoves(lateGameBoard, 0)
  //=> [2]

Whew! We’re almost done writing the things we would need to handle game mechanics if we were writing an Ayoayo game. The final thing is the end condition. If a player has no stones in their row at the beginning of their turn, their opponent collects all of the stones left on the board, and the game ends.

Let’s implement that.

Everything ends, not just games, but even stars: In 1054 AD, during the Song dynasty, Chinese astronomers spotted a bright new star in the night sky. This newcomer turned out to be a violent explosion within the Milky Way, caused by the spectacular death of a star some 1600 light-years away. This explosion created one of the most well-studied and beautiful objects in the night sky–the Crab Nebula. (More information.)

ending the game

We said above that “If a player has no stones in their row at the beginning of their turn, their opponent collects all of the stones left on the board, and the game ends.” That is equivalent to saying that “If, after making a permissible move, your opponent’s row is empty, you capture all of the stones in your row, and then the game ends.”

Put that way, we don’t need a brand new function, we can update handleCaptures. That function is already big enough and has one clear responsibility, handling the ordinary kind of capture. So let’s extract that and make it a helper, then write a new function to handle captures after completing a turn:

function handleCapturesInTurn(beforeBoard, beforeScore, startPit, endPit) {
  const endedOnThePlayersSide = startPit < 6 === endPit < 6;

  if (endedOnThePlayersSide) {
    const pitOnOpponentsSide = 11 - endPit;
    const afterBoard = beforeBoard.slice(0);
    const playerNumber = ownerOf(startPit);
    const afterScore = Object.assign(
      beforeScore,
      { [playerNumber]: beforeScore[playerNumber] + beforeBoard[pitOnOpponentsSide] }
    );
    afterBoard[pitOnOpponentsSide] = 0;

    return [afterBoard, afterScore];
  } else {
    return [beforeBoard, beforeScore];
  }
}

function handleGameEnd(beforeBoard, beforeScore, playerWhoJustMoved) {
  // Write function here!
}

function handleCaptures(beforeBoard, beforeScore, startPit, endPit) {
  const [afterCapturesInTurn, afterScoreInTurn] =
    handleCapturesInTurn(beforeBoard, beforeScore, startPit, endPit);
  const playerWhoJustMoved = ownerOf(startPit);
  const [afterTurn, afterScore] = handleGameEnd(afterCapturesInTurn, afterScoreInTurn, playerWhoJustMoved);
  const isOver = (afterScore[0] + afterScore[1]) === 48;

  return [afterTurn, afterScore, isOver];
}

function sowAndCapture(beforePits, beforeScore, startPit) {
  const [afterSowing, endPit] = relaySow(beforePits, startPit);
  const [afterTurn, scoreAfter, isOver] = handleCaptures(afterSowing, beforeScore, startPit, endPit);

  return [afterTurn, scoreAfter, isOver];
}

And now let’s write handleGameEnd. For starters, we check whether the other player has moves, if they do, there is no effect:

function otherPlayerFor(player) {
  return 1 - player;
}

function handleGameEnd(beforeBoard, beforeScore, playerWhoJustMoved) {
  const otherPlayerNumber = otherPlayerFor(playerWhoJustMoved);
  const otherPlayerHasMoves = atLeastOnePossibleMove(beforeBoard, otherPlayer);

  if (otherPlayerHasMoves) {
    return [beforeBoard, beforeScore];
  } else {
    // Capture everything else!
  }
}

If they don’t, we capture every stone on the player’s side. We can use our encapsulation pattern to avoid [first, rest]:

function handleGameEnd(beforeBoard, beforeScore, playerWhoJustMoved) {
  const otherPlayer = otherPlayerFor(playerWhoJustMoved);
  const otherPlayerHasMoves = atLeastOnePossibleMove(beforeBoard, otherPlayer);

  if (otherPlayerHasMoves) {
    return [beforeBoard, beforeScore];
  } else {
    const disposablePits = pitsBelongingTo(playerWhoJustMoved).slice(0);
    const stonesRemaining = countStones(beforeBoard, disposablePits);

    const playerWhoJustMovedScore = beforeScore[playerWhoJustMoved] + stonesRemaining;

    const finalScore = {
      [playerWhoJustMoved]: playerWhoJustMovedScore,
      [otherPlayer]: beforeScore[otherPlayer]
    };

    return [
      [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
      finalScore
    ];
  }

  function countStones(board, disposablePits, runningTotal = 0) {
    if (pits.length === 0) {
      return runningTotal;
    } else {
    	const first = disposablePits.slice(0);

    	return countStones(board, rest, runningTotal + board[first]);
    }
  }
}

And we can do an “integration test,” running our code from end to end:

const lateGameBoard = [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0];
const lateGameScore = { 0: 40, 1: 5 };

let [afterTurn, afterScore, isOver] = sowAndCapture(lateGameBoard, lateGameScore, 2);

afterTurn
  //=> [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

afterScore
  //=> { 0: 43, 1: 5 }

isOver
  //=> true

const notOverBoard = [1, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0];
const notOverScore = { 0: 39, 1: 5 }

[afterTurn, afterScore, isOver] = sowAndCapture(notOverScore, lateGameScore, 2);

afterTurn
  //=> [1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0]

afterScore
  //=> { 0: 39, 1: 5 }

isOver
  //=> false

Success!

taking stock of what we’ve learned

We’ve written a fair amount of code, and along the way taken a few digressions. Let’s take our “learnings” and put them together in a more structured fashion.

It’s time to talk about recursion a little more formally.

Ayoayo and Linear Recursion

what is linear recursion?

In programming, a recursive function is a function that invokes itself directly or indirectly. For example, a merge sort divides lists into two halves, then calls itself to sort each of the halves before calling merge to merge them back together in order.

function mergeSort (list) {
  const listLength = list.length;

  if (listLength <= 1) {
    return list;
  } else {
    const cutPoint =  Math.floor(listLength/2);

    const half = list.slice(0, cutPoint);
    const otherHalf = list.slice(cutPoint);

    const sortedHalf = mergeSort(half);
    const sortedOtherHalf = mergeSort(otherHalf);

    return merge(sortedHalf, sortedOtherHalf);
  }
}

function merge (...mutableLists) {
  return recursiveMerge(mutableLists, []);

  function recursiveMerge (mutableLists, mutableSoFar) {
    const listsWithElements = mutableLists.filter(l => l.length > 0);

    if (listsWithElements.length === 0) {
      return mutableSoFar;
    } else if (listsWithElements.length === 1) {
      return mutableSoFar.concat(listsWithElements[0]);
    } else {
      const firsts = listsWithElements.map(l => l[0]);
      const lowest = Math.min(...firsts);
      const indexOfLowest = firsts.indexOf(lowest);
      const listWithLowest = listsWithElements[indexOfLowest];

      listWithLowest.shift();
      mutableSoFar.push(lowest);

      return recursiveMerge(listsWithElements, mutableSoFar)
    }
  }
}

console.log(mergeSort([7, 1, 3, 4, 5, 0, 2, 6]))
  //=> [0, 1, 2, 3, 4, 5, 6, 7]

If we draw the call graph for recursiveMerge, it’s a tree with two branches per node. We say that it’s bi-recursive.

But if we draw the call tree for any one invocation of recursiveMerge within merge, it’s a straight line:

A linearly recursive function is a function where each invocation that invokes itself (directly or indirectly) at most once before returning. Therefore, recursiveMerge is a linearly recursive function.

Linear recursion is interesting, and here’s why…

Linear recursion is interesting, and so is this photograph showing a spiral bridge of young stars between two ancient galaxies.

At the center of the bull’s-eye of blue, gravitationally lensed filaments lies a pair of elliptical galaxies that are also exhibiting some interesting features. A 100,000-light-year-long structure that looks like a string of pearls twisted into a corkscrew shape winds around the cores of the two massive galaxies. The “pearls” are superclusters of blazing, blue-white, newly born stars. These super star clusters are evenly spaced along the chain at separations of 3,000 light-years from one another.

why linear recursion is interesting

Linear recursion is particularly interesting because it is computationally equivalent to iteration. Any function that is linearly recursive, can be rewritten as a function that iterates but is not recursive. The converse is also true: Any piece of code that iterates, can be rewritten as an invocation of a linearly recursive function that does not iterate.

There are important reasons why this equivalence matters to fundamental computer science theory: It shows that if we have functions and function invocation, we don’t need to add iteration to prove things about computability. But that isn’t what we’re going to look at here.

Consider a hypothetical for loop inside a function:

function doSomethingOrOther (collection) {
  let someVar = somethingOrOther();

  // something happens before the loop

  // frobbish the collection:
  for (const element of collection) {
    // something happens inside the loop to
    // frobbish the collection, element by element
  }

  // something happens after the loop
}

What kinds of things can happen inside the loop to “frobbish the collection?” Almost anything can happen inside the loop! Code can continue, jumping to the next iteration. Code can break from the loop, jumping straight to // something happens after the loop. Code can read variables from outside the loop, and also write to those variables.

Code inside loops can be very tightly coupled to the code outside of the loop. That’s kind of the whole point, code inside a loop is rarely thought of as being “separate” from the rest of the code in a function, so why shouldn’t it be tightly coupled with that code?

We’ve seen a lot of code so far, so let’s continue with this hypothetical and completely code-free example. Let’s imagine we refactor the code to extract the loop into a frobbish function:

function frobbish (collection, someVar) {
  // something happens inside the function to
  // frobbish the collection, element by element
};

function doSomethingOrOther (collection) {
  let someVar = somethingOrOther();

  // something happens before the loop

  // frobbish the collection:
  const frobbishedCollection =
    frobbish(collection, someVar);

  // something happens after the loop
}

We get an immediate win, and I don’t mean that our function is shorter: When we lose the linear flow of a function, it’s harder to read. We have to get something in exchange, and what we get is actually quite powerful: By extracting the function, it is now clear what our frobbish code reads (collection and someVar), and what it writes (just collection).

If We use a fancy editor that has an “extract helper function” refactoring capability, it can extract almost any chunk of code, but if the code was tightly coupled to the rest of the function, we’ll get four or five parameters going in, and another four or five coming out.

Whether we do it by hand or not, extracting the function takes what was always there–the dependencies–and makes them explicit. That can encourage us to rewrite the code to eliminate the dependencies, and if we don’t, at least it can help us understand what effect that code can have on the rest of the function.

But there’s more.

function frobbish (collection, someVar) {
  // something happens inside the function to
  // frobbish the collection, element by element
};

Code inside the function can become tightly coupled to itself. It can read and write anything it wants. It can set up some variables and modify them inside a loop. In fact, we can move all of the coupling into our extracted function that we wanted to get rid of.

But what if we refactor that function–which was designed to replicate a single piece of iteration–to be linearly recursive?

function frobbish (collection, someVar) {
  if (collection.length === 0) {
    // handle the degenerate case
  } else {
    const [first, ...rest] = collection;

    // frobbish the first element, then
    // combine it with frobbish(rest, someVar)
  }
};

Recall above where we espoused the value of pure functions as being decoupled from themselves. Doing the same with a linearly recursive function forces us to decouple frobbish from itself, making any dependencies explicit, and encouraging us to find ways to eliminate as many dependencies as possible.

In sum, A tremendous value of expressing code as linear recursion with dependency-free functions rather than as iteration, is that it makes dependencies explicit. That in turn helps us eliminate them.

Now we could go off on a tangent about how to refactor iteration into linear recursion, or the reverse, how to refactor linear recursion into iteration. But let’s sum up what we’ve gathered from this exercise.

the finish line

We learned that while we can refactor functions with dependencies into functions without dependencies (via the “dependency injection” pattern), we can also use what we learned to write them functions without dependencies in the first place. The important thing is not the specifics of the refactoring, but what we are trying to achieve.

It’s the same with linear recursion. The important thing is to understand what we’re trying to achieve: low coupling.

We don’t need to write everything with iteration and then refactor to linear recursion: We can just write it as linear recursion in the first place. When we take a “linear-recursion-first” approach, we naturally end up with code that has high cohesion and low coupling. Linear recursion makes that easy.

Of course, there are real tradeoffs. Constantly making copies of arrays is expensive: We have to select data structures that are less wasteful when we slice them up, or use patterns (like iterators) that allow us to write the equivalent code that doesn’t need to do things like copy arrays.

Or we have to learn how to write tail-recursive functions, and use a language implementation that optimizes our functions for us.

Or we have to get it working with linear recursion, and then refactor it back to iteration. This is very interesting, because if we write it with linear recursion, and then refactor it back to iteration, it will retain its uncoupled form. Of course, over time code can accrete and become coupled.

These and other considerations are beyond the scope of this essay. But starting with linear recursion, and then refactoring to iterative code, is an excellent way to ensure that the iteration we do implement is clean and coupling-free.

And in the fullness of time, we will start writing iterative code that is clean and decoupled from the outset, thanks to our familiarity and practice with writing linearly recursive functions. Linear recursion–like dependency-free functions–is a powerful tool for learning what kinds of iterative code is going to be easiest to understand and work with.

THE END

Appendix: The completed code

Notes