Dev Blog | Guess the Number, Part 4

Currently, our Guess the Numbers game only works for 1 round: the computer makes a guess, the player answers, and the game ends. In this tutorial, we’ll keep the game going until the answer is reached, which we can accomplish using a loop.

Basically, we would like to accomplish this repetitive behavior:

I've thought of a number between 0 to 99... can you guess it?
> 45
Bigger!
> 78
Smaller!
> 50
Bigger!
> 60
Smaller!
...continue until answer is found...

As Clojure uses a concept called recursion to implement looping, let’s take a look at this concept first.

Recursion

In programming, recursion is the process of having a function call itself. Why would we want a function to do this? A recursive approach allows us to break up a problem into smaller parts that can each be solved using the same solution.

As a toy example, given the multiplication problem:

500 * 332 * 641.5 * 0.132 = ?

We can divide it into the following problems:

500 * 332 = ?
? * 641.5 = ??
?? * 0.132 = ???

where I use the ? symbol to indicate the answer found for line 1, ?? for line 2 and so on. For each line, we only have to solve the problem of multiplying two numbers together. We accomplish this in Clojure with the following code:

(defn multiply-numbers [total numbers]
  (if (empty? numbers)
    total
    (multiply-numbers
     (* total (first numbers))
     (rest numbers))))

Testing the function:

=> (multiply-numbers 1 [1 2 3 4])
24
=> (multiply-numbers 1 [500 332 641.5 0.132])
1.4056548E7

The main work is done on line 5 of the program, where we multiply the running total with the first element in the list. Then, we pass the result, along with the rest of the list, back into multiply-numbers. Every time multiply-numbers is called, we check if the numbers list is empty. If so, we return total as the answer.

What we’ve implemented so far already looks like looping: the function will multiply all numbers with a running total until all given numbers have been exhausted. However, there are limitations with this approach in Clojure.

The stack overflow problem

In most software, when a call to a function is made, the computer will store some bookkeeping information, such as how to return to the original calling function, in a storage structure known as a stack. This information is kept until the called function ends. Since the stack has a finite amount of space, can you guess what will happen when a function keeps on calling itself without returning? Let’s write a program to find out:

(defn die [total]
  (println total)
  (die (inc total)))

=> (die 0)
0
1
2
...
9693
9694
9695
StackOverflowError   clojure.walk/stringify-keys/fn--6998 (walk.clj:105)

We’ve just triggered a nasty error called a stack overflow, which occurs because the stack limit has been reached. The actual limit seems to be dependent on several factors such as the OS and program configuration, but it’s not uncommon for loops in games to reach the stack limit no matter how large. We could even reach this limit with our multiply-numbers function:

=> (multiply-numbers 1 (repeat 1000 1))
1
=> (multiply-numbers 1 (repeat 9999 1))
StackOverflowError   clojure.core/cons (core.clj:29)

The first repeat gives us a sequence containing 1000 1s, while the second repeat gives us a sequence containing 9999 1s.

loop and recur

Fortunately, Clojure gives us the loop special form to bypass this limitation. From the docs:

loop
clojure.core

    (loop bindings & body)

Evaluates the exprs in a lexical context in which the symbols in the
binding-forms are bound to their respective init-exprs or parts therein.
Acts as a recur target.

First, we’ll convert our multiply-numbers function to see how loop works:

(defn multiply-numbers [numbers]
  (loop [total 1
         numbers numbers]
    (if (empty? numbers)
      total
      (recur
       (* total (first numbers))
       (rest numbers)))))

=> (multiply-numbers [2 3 4 5])
120
=> (multiply-numbers (repeat 9999 1))
1

The parameters to loop are very similar to the let form. The first parameter lets you create bindings local to the loop form, while the body parameter can take in any number of forms to create the body of the loop. loop works hand in hand with recur, another special form which reruns the loop while replacing the loop’s local bindings with fresh arguments. In effect, recur acts like a new “function call” to the loop, passing in the running total and the remaining numbers as parameters. This also means that recur must pass the same number of arguments that were bound by loop initially.

There is one condition for the use of recur: recur must be in the tail position of the loop, meaning there should be no more forms that run after recur. This restriction allows Clojure to determine that there is no need to allocate more space on the stack.

Putting it together

Finally, we have the pieces we need to finish the first part of our game, whew! Modify -main in core.clj as follows:

(defn -main []
  (println "Think of a number between 0 to 99 and I'll try to guess it!")
  (loop [minimum 0
         maximum 99]
    (let [guess (int (/ (- maximum minimum) 2))]
      (println "My guess is:" guess)
      (println "1. Bigger")
      (println "2. Smaller")
      (println "3. That's correct!")
      (print "> ")
      (flush)
      (condp = (Integer/parseInt (read-line))
        1 (recur guess maximum)
        2 (recur minimum guess)
        3 (println "All right!!!")
        (do (println "I didn't understand your answer...")
            (recur minimum maximum))))))

This time, the game runs until the computer guesses the right answer:

Think of a number between 0 to 99 and I'll try to guess it!
My guess is... 49.
1. Bigger
2. Smaller
3. That's correct!
> 1
My guess is... 25.
1. Bigger
2. Smaller
3. That's correct!
> 1
My guess is... 37.
1. Bigger
2. Smaller
3. That's correct!
>

But wait, there’s something wrong with the computer’s guesses: they keep getting smaller although the player’s answer is larger! That’s because a bug has been present in our program since the beginning: we’ve not added the minimum guess to the calculation on line 5. This bug hasn’t been obvious until now since minimum has always been 0. The actual fix for this bug is left to you, the reader :)

Now, compare our Clojure program to the one in the previous tutorial.

line 3: We’ve shifted minimum and maximum into local bindings of the loop.

line 13, 14: After receiving the player’s input at line 12, we re-run the loop using recur while replacing either the maximum or minimum of the computer’s range of guesses.

line 15: If the player’s input was not an allowed answer, we handle it by printing an error message and recurring with the same range again, using a do special form. We use do because condp only allows 1 form in that return position, but do allows us to execute several forms while returning the last form within do.

Next time, we’ll finish off our program by allowing the player to guess the number instead.

clojure