How to Use Recursion in Scala

When learning about recursion, a common example is the Fibonacci sequence. In simple terms, we say that the nth Fibonacci number is equal to the sum on the (n-1)th Fibonacci number and the (n-2)th Fibonacci number. By adding in the rule that the 0th and 1st Fibonacci numbers are 0 and 1 respectively, it’s possible to determine the value of any number in the series. This is pretty simple to define:

  def fib(n:Long):Long = n match {
    case 0 => 0
    case 1 => 1
    case _ => fib(n - 1) + fib(n - 2)

This is a really beautiful function because it purely describes the rules above. If n is 0 or 1, we exit the function otherwise we recursively calculate the (n-1)th and (n-2)th Fibonacci numbers. Unfortunately, pure functions are not always efficient in Scala.

Consider how the computer would work through fib(4). It must traverse a tree of functions until it gets to either fib(1) or fib(0):

                 /         \
          fib(3)              fib(2)
          /   \               /   \
     fib(2)    fib(1)    fib(1)    fib(0)
     /   \
fib(1)    fib(0)

Since we told the computer the values of fib(1) and fib(0), it can finally calculate the total by summing all of these together–3.

This tree quickly increases in complexity (at the rate of 2n) to the point where the function is almost unusable for even small numbers like 30 or 50. While most Scala programmers seem to agree that a functional style is preferable to an imperative style, the language itself allows us to do either. Should we sacrifice beauty for practicality? Let’s consider an imperative approach.

  def fib() = {
    var n = 4
    var a = 0
    var b = 1
    var c = 1
    while(n > 0) {
      a = b
      b = c
      c = a + b
      n = n - 1

This code is a bit harder to read. To start out with, we have to declare our n value inside the function which feels wrong. Then we seed a few variables with the start of the Fibonacci sequence: 0, 1, 1. Here’s a chart to show how the computer processes this loop:


Notice how in each iteration of the loop the old value of a drops off? This saves both time and memory. It saves time because there are fewer iterations of the loop to run through (just 4 instead of 8), and it saves memory because we are only keeping track of a, b, c, and n instead of all the branches of the tree in the previous function.

So while we now have an efficient method, it feels a bit dirty and is not easy to understand simply by looking at the code. Is there a way to balance intuitiveness and efficiency? In fact, we can take advantage of tail recursion in Scala.

  def fib(n:Long):Long = {
    def fibHelper(n:Long, a:Long, b:Long):Long = {
      if(n == 0) a
      else fibHelper(n - 1, b, a + b)
    return fibHelper(n, 0, 1)

This function is “tail recursive” because it is recursive (fibHelper calls itself), but the computer only needs to keep track of the result of the previous call (the “tail”). Just like we saw in the imperative approach, this function “forgets” about the previous a value. By applying a tail recursive approach, we get the performance of the imperative method but with a relatively “pure” function. The tail recursive function does not resort to modifying variables nor does it require n to be defined inside the method.

Here’s a performance comparison for calculating Fibonacci 35:

TypeStack Memory (bytes)Time (ms)
Naive Recursion7889278.8502
Tail Recursion52480.0037

Tail recursion is so preferable that Scala will try to optimize them automatically when compiling to bytecode. On my version (2.10.4), this function was automatically optimized. However, you can provide a compiler hint with the @tailrec annotation right above the fib method. This will force the compiler to optimize the function accordingly (and will throw a compile-time error if the function is not truly tail-recursive).

Much of this was inspired by the discussion of recursion in Structure and Interpretation of Computer Programs. For more details, I highly recommend this book.

Implementing Minimax in Scala: Alpha-Beta Pruning

Last time, we built a naive minimax algorithm in Scala. While it was effective, it was unfortunately very slow. To increase the performance of the algorithm, we’ll implement a common variant of minimax with what is called “alpha-beta pruning”. Again, if you want to see the full code right away, head over to GitHub.

Recall that the minimax algorithm works by playing out all possible games given a starting game state. During the course of the analysis, undoubtably paths will be encountered that have no hope of resulting in victory. Alpha-beta pruning removes those as possible paths and stops searching any deeper down those paths. This is accomplished by applying a check for each iteration to see if the score returned is worse than the best score encountered.

  private def minimax(state:GameState):Int = {
    minimize(state, maxDepth, Integer.MIN_VALUE, Integer.MAX_VALUE)

  private def minimize(state:GameState, depth:Int, alpha:Int, beta:Int):Int = {
    if(state.isTerminal || depth == 0) return state.hVal
    var newBeta = beta
    state.availableMoves.foreach(move => {
      val newState = state.makeMove(move)
      newBeta = math.min(beta, maximize(newState, depth - 1, alpha, newBeta))
      if (alpha >= newBeta) return alpha

You should see a lot similarity here. The big difference is that now we instead of just accepting the best result as the result of maximize function, β is now the smaller of the previous β value or the result of maximize. Next comes the critical check. If α ≥ β we immediately exit the function and return α as the best possible score.

The maximize function is of course quite similar, except this time we return β if no better scores are are found.

  private def maximize(state:GameState, depth:Int, alpha:Int, beta:Int):Int = {
    if(state.isTerminal || depth == 0) return state.hVal
    var newAlpha = alpha
    state.availableMoves.foreach(move => {
      val newState = state.makeMove(move)
      newAlpha = math.max(newAlpha, minimize(newState, depth - 1, newAlpha, beta))
      if (newAlpha >= beta) return beta

When I ran this code in the same game as the naive algorithm, the processing time was an order of magnitude faster.

Implementing Minimax in Scala: Naive Minimax

Minimax is algorithm commonly used by AI in two-player games to determine the best possible move given a current state of the game. It gets its name from the intuitive concept that a player wants to minimize his opponent’s score while maximizing his own score. The core of this algorithm essentially plays out all of the possible games until the game is over. Then the play that resulted in the best end game (minimize opponent’s score, maximize player’s score) is chosen. If you want to see the full code right away, head over to GitHub. Otherwise, read on and let’s see how this is implemented.

  def play(state:GameState):(Int, Int) = {
    val moveScores = {
      for {
        move <- state.availableMoves
      } yield move -> minimax(state.makeMove(move))
    val bestMove = moveScores.minBy(_._2)._1

We start with a GameState which I have intentionally left out of this post. You are free to implement GameState however you see fit (although stay tuned for an actual game that uses this algorithm). We then iterate over all of the available moves in the game state and return a key->value pair of move->score. The best move is the one that minimizes the opponent’s score. So given the list of move->score pairs, we find the pair with the smallest score and return the move. Scala’s syntax for this last bit is pretty terse: moveScores.minBy(_._2)._1. The _. was confusing to me at first, but the underscore could be replaced by any identifier, such as “pair” or “moveToScoreTuple”. The use of the underscore is to imply that we do not particularly care to name the pair because we never need to refer to the pair by name.

If you recall, I said earlier that minimax plays out all possible games until the end. In practice, this would take far too long. Consider a game like Chess in which there are approximately 10120 possible games (more than the number of atoms in the universe). Playing out all of the games would be impractical. So we usually implement a “depth” concept in minimax which tells the algorithm how many moves it is allowed to play. When the depth is reached, the algorithm returns the score of that game state (even though the game is not necessarily over). We kickoff the search using the chosen depth:

  val maxDepth = 3

  private def minimax(state:GameState):Int = {
    minimize(state, maxDepth)

  private def minimize(state:GameState, depth:Int):Int = {
    if(state.isTerminal || depth == 0) return state.hVal
    var bestResult = Integer.MAX_VALUE
    state.availableMoves.foreach(move => {
      val newState = state.makeMove(move)
      val bestChildResult = maximize(newState, depth - 1)
      bestResult = math.min(bestResult, bestChildResult)

Note that the minimax function returns an Int. This is score of the game state in which the algorithm terminated. To start the process we jump down into the minimize function.

Immediately we want to see if the game is over (state.isTerminal) or if the algorithm has reached the maximum number of moves (depth == 0). If either of those conditions are true we return the “heuristic value” (hVal) of that state, which is the score. If neither of those conditions are true, we continue as normal.

Remember at this point we already made one move (in the play() function), so we’re now evaluating the plays the opponent will make. Since we are trying to minimize the opponent’s score, the worst outcome for us is one in which the opponent scores +∞, which we represent by Integer.MAX_VALUE. We want to see if there is any move in which our opponent will score lower than +∞, so we loop over the available moves our opponent could make in this game state. Of course, our opponent is also trying to win, so the best play for the opponent is the one that maximizes his score! More on this in a moment, but that is the reason why we run val bestChildResult = maximize(newState, depth - 1). Finally we update the bestResult to be the smaller of the current bestResult and the bestChildResult. After checking all possibilities, we have minimized the score and return bestResult.

Now we need to see the other half of the algorithm.

  private def maximize(state:GameState, depth:Int):Int = {
    if(state.isTerminal || depth == 0) return state.hVal
    var bestResult = Integer.MIN_VALUE
    state.availableMoves.foreach(move => {
      val newState = state.makeMove(move)
      val bestChildResult = minimize(newState, depth - 1)
      bestResult = math.max(bestResult, bestChildResult)

No surprise that is looks very similar! All we’re doing is flipping a few things around. This time, the worst outcome is the one in which we score -∞. Additionally, we want to return the larger of the bestResult and bestChildResult because we are trying to maximize our score.

Looking at both sides of the algorithm, we can now see the flip-flop that occurs. The minimize function calls maximize and vice versa. This flip back and forth simulates the two players taking alternating turns. Each player wants to make the move that is best for him and worst for his opponent. To increase the speed of the algorithm, we limit the number of possible moves which is why each successive call is made with depth - 1.

Unfortunately, this is still pretty slow. In the next post we’ll see how we can save the algorithm some time by not evaluating games that have already been lost.

Raspberry Pi Minimally Required Boot Files

I got a Raspberry Pi for Christmas so naturally I wanted to get started hacking on it right away. But the tutorials I found online assume you’re starting with an SD card with a kernel like NOOBS or Raspbian installed. I was going through the Baking Pi tutorials to write your own kernel, so I had no use for another kernel.

I could not easily find just the Raspberry Pi boot files. So to save others some time, I created a github repo for just that purpose. Instructions and files are available at Raspberry Pi Minimal Boot.

Just a quick post for now, but expect to see more about Raspberry Pi in the coming weeks.

NaNoGenMo 2014 Dev Diary #3: Results

NaNoGenMo is an idea created by Darius Kazemi to parody NaNoWriWo. Instead of writing a novel, developers write programs to generate 50k+ word “novels”. This series of posts will document my participation throughout the month.

With the scaffolding in place that I described in my last post, I was able to pretty easily substitute the sample words for real words. The most significant change I made was implementing a simple cache. There’s no reason to search the graph and calculate the probabilities for the same word more than once.

As I expected, this method resulted in mostly gibberish. The reason for this is because using only word concordances means that the only guaranteed grammatical correctness is between each pair of words. There is no guarantee that the sentence as a whole is grammatically correct. Nonetheless, I did end up with some humorous text. Here are just a few of my favorites.






If I redid this, I would want to find a cleaner data source. My source was filled with typos, inconsistencies, and non-standard punctuation. This led to some difficulties seeding the database. Also I think I would count “…” as its own distinct sentence-terminator. Finally, a similar approach that would have less gibberish would be using Markov chains instead of simple concordances.

All of my code and the final “Missing Season” is available on github.