Extracted from:

Functional Programming Patterns
in Scala and Clojure
Write Lean Programs for the JVM

This PDF file contains pages extracted from Functional Programming Patterns in
Scala and Clojure, published by the Pragmatic Bookshelf. For more informationor to purchase a paperback or PDF copy, please visit http://www.pragprog.com.
Note: This extract contains some colored text (particularly in code listing). Thisis available only in online versions of the books. The printed versions are blackand white. Pagination might vary between the online and printed versions; thecontent is otherwise identical.
Copyright © 2013 The Pragmatic Programmers, LLC.
All rights reserved.
No part of this publication may be reproduced, stored in a retrieval system, or transmitted,
in any form, or by any means, electronic, mechanical, photocopying, recording, or otherwise,
without the prior consent of the publisher.

The Pragmatic Bookshelf
Dallas, Texas • Raleigh, North Carolina

Functional Programming Patterns
in Scala and Clojure
Write Lean Programs for the JVMMichael Bevilacqua-Linn

The Pragmatic Bookshelf
Dallas, Texas • Raleigh, North Carolina

Pattern 12Tail Recursion
IntentTo repeat a computation without using mutable state and without overflowing
the stackOverview
Iteration is an imperative technique that requires mutable state. For example,
let’s examine a trivial problem, writing a function that will calculate the sumfrom one up to an arbitrary number, inclusive. The code below does just that,
but it requires both i and sum to be mutable:
JavaExamples/src/main/java/com/mblinn/functional/tailrecursion/Sum.java
public static int sum(int upTo) {int sum = 0;
for (int i = 0; i <= upTo; i++)sum += i;return sum;}

Since the functional world emphasizes immutability, iteration is out. In its
place, we can use recursion, which does not require immutability. Recursion
has its own problems, though; in particular, each recursive call will lead toanother frame on the program’s call stack.
To get around that, we can use a particular form of recursion called tailrecursion, which can be optimized to use a single frame on the stack, a process
known as tail call optimization or TCO.
Let’s think about how we’d write the sum() as a recursive function, sumRecursive().
First, we need to decide when our recursion should stop and start. Since
we’re summing together all numbers stopping at some arbitrary number, it
makes sense to work down from that number and stop at zero. This stopping
point is known as our base case.
Next we need to figure out what to do to perform the actual computation. In
this case, we take the number we’re currently working on and add it to theresults of calling tailRecursive() with that number minus one. Eventually, we getdown to our base case of zero, at which point the stack unwinds, returning• Click HERE to purchase this book now. discuss•6partial sums as it goes, until it reaches the top and returns the final sum.
The code below demonstrates this solution:
JavaExamples/src/main/java/com/mblinn/functional/tailrecursion/Sum.java
public static int sumRecursive(int upTo) {if (upTo == 0)
return 0;
else
return upTo + sumRecursive(upTo - 1);}

There’s a problem with this, though. Each recursive call adds a frame to thestack, which means this solution takes memory proportional to the size ofthe sequence we’re summing, as shown in the following figure.

Figure 10—Simple Stack. An illustration of the stack during normal recursive calls—eachrecursive call adds a call to the stack; these frames represent memory that cannot bereclaimed until after the recursion is done.
Clearly this isn’t practical, but we can do better. The ultimate cause for
exploding stack use is that each time we make a recursive call, we need theresult of that call to finish the computation we’re doing in the current call.
This means that the runtime has no choice but to store the intermediate
results on the stack.
If we were to make sure that the recursive call was the last thing that happensin each branch of the function, known as the tail position, this would no longer
be the case. Doing so requires us to take the intermediate values that wereformerly stored on the stack and pass them through the call chain. The code
below illustrates this:• Click HERE to purchase this book now. discussTail Recursion • 7
JavaExamples/src/main/java/com/mblinn/functional/tailrecursion/Sum.java
public static int sumTailRecursive(int upTo, int currentSum) {if (upTo == 0)
return currentSum;
else
return sumTailRecursive(upTo - 1, currentSum + upTo);}

Once we rewrite the function to be tail recursive, it’s possible to use TCO torun it in only a single stack frame, as shown in this figure.

Figure 11—Stack with TCO. With TCO, recursive calls in the tail position don’t generate a
new stack frame. Instead, each call uses the existing stack frame, removing whatever data
was there from the previous call.
Unfortunately, the JVM doesn’t support TCO directly, so Scala and Clojure
need to use some tricks to compile their tail recursive calls down to the same
bytecode used for iteration. In Clojure’s case, this is done by providing two
special forms, loop and recur, instead of using general purpose function calls.
In Scala’s case, the Scala compiler will attempt to translate tail recursive calls
into iteration behind the scenes, and Scala provides an annotation, @tailrec,that can be placed on functions that are meant to be used in a tail recursivemanner. If the function is called recursively without being in the tail position,
the compiler will generate an error.

Code Sample: Recursive People
Let’s take a look at a recursive solution to a simple problem. We’ve got asequence of first names and a sequence of last names, and we want to put
them together to make people. To solve this, we need to go through bothsequences in lock step. We’ll assume that some other part of the program
has verified that the two sequences are of the same size.
At each step in the recursion, we’ll take the first element in both sequences
and put them together to form a full name. We’ll then pass the rest of eachsequence onto the next recursive call along with a sequence of the people
we’ve formed so far. Let’s see how it looks in Scala.

• Click HERE to purchase this book now. discuss•8In Scala
The first thing we’ll need is a Scala case class to represent our people. Here
we’ve got one with a first and a last name:ScalaExamples/src/main/scala/com/mblinn/mbfpp/functional/tr/Names.scalacase class Person(firstNames: String, lastNames: String)

Next up is our recursive function itself. This is actually split into two functions.
The first is a function named makePeople, which takes in two sequences, firstNames
and lastNames. The second is a helper function nested inside of makePeople, whichadds an additional argument used to pass the list of people through recursive
calls. Let’s take a look at the whole function before we break it down into
smaller parts:
ScalaExamples/src/main/scala/com/mblinn/mbfpp/functional/tr/Names.scaladef makePeople(firstNames: Seq[String], lastNames: Seq[String]) = {@tailrecdef helper(firstNames: Seq[String], lastNames: Seq[String],people: Vector[Person]): Seq[Person] =if (firstNames.isEmpty)
peopleelse {
val newPerson = Person(firstNames.head, lastNames.head)
helper(firstNames.tail, lastNames.tail, people :+ newPerson)}
helper(firstNames, lastNames, Vector[Person]())}

First, let’s examine the function signature of makePeople:
def makePeople(firstNames: Seq[String], lastNames: Seq[String]) = {«function-body»}

This just says that makePeople takes two Seqs of String. Since we don’t specify areturn type, the compiler will infer it from the function body.
Next up, let’s look at the signature of the helper function. This function isresponsible for the actual tail recursive calls. The helper function is annotatedwith a @tailrec annotation, which makes the compiler generate an error if it’scalled recursively but not tail recursively. The function signature simply adds
an additional argument, the people vector, which will accumulate results
through recursive calls.
Notice that we specified a return type here, though we generally omit it in our
Scala examples. This is because the compiler can’t infer types for recursively
called functions.

• Click HERE to purchase this book now. discussTail Recursion • 9
def helper(firstNames: Seq[String], lastNames: Seq[String],people: Vector[Person]): Seq[Person] =«function-body»

Now the body for helper. If the firstNames sequence is empty, we return the listof people we’ve built up. Otherwise, we pick the first first name and the first
last name off of their respective sequences, create a Person out of them, andcall the helper function again with the tail of the two sequences and the new
person appended to the list of people:
if (firstNames.isEmpty)
peopleelse {
val newPerson = Person(firstNames.head, lastNames.head)
helper(firstNames.tail, lastNames.tail, people :+ newPerson)}

Finally, we simply call helper with the sequences of names and an empty Vector
to hold our people:
helper(firstNames, lastNames, Vector[Person]())

One closing note on the syntax: using some of Scala’s object-oriented features,
namely methods, would let us cut out some of the verbosity that comes alongwith a recursive function definition. The method signatures would look likethis:def makePeopleMethod(firstNames: Seq[String], lastNames: Seq[String]) = {@tailrec
def helper(firstNames: Seq[String], lastNames: Seq[String],
people: Vector[Person]): Seq[Person] =«method-body»}}

Since we’re sticking mainly to the functional bits of Scala in this book, we’reusing functions for most of the examples rather than methods. Methods canoften be used as higher-order functions in Scala, but it can sometimes beawkward to do so.

In Clojure
In Clojure, tail recursive calls are never optimized, so even a tail recursive
call will end up consuming a stack frame. Instead of providing TCO, Clojure
gives us two forms, loop and recur. The loop form defines a recursion point, andthe keyword recur jumps back to it, passing it new values.
In practice, this looks almost exactly like defining a private helper function
does, so the form of our solution is very similar to the Scala solution, though• Click HERE to purchase this book now. discuss• 10we’ll use a simple map to store our people, as is standard in Clojure. Let’stake a look at the code:
ClojureExamples/src/mbfpp/functional/tr/names.clj(defn make-people [first-names last-names](loop [first-names first-names last-names last-names people []](if (seq first-names)(recur(rest first-names)(rest last-names)(conjpeople{:first (first first-names) :last (first last-names)}))people)))

The first interesting bit of code here is the loop declaration. Here, we define
our recursion point and the values we’ll start our recursion at: the passed-in
sequences of first and last names and an empty vector we’ll use to accumulate
people as we recur.
(loop [first-names first-names last-names last-names people []]«loop-body»)

The code snippet first-names first-names last-names last-names people [] might look alittle funny, but all it’s doing is initializing the first-names and last-names that
we’re defining in the loop to be the values that were passed into the function
and the people to an empty vector.
The bulk of the example is in the if expression. If the sequence of first names
still has items in it, then we take the first item from each sequence, create amap to represent the person, and conj it onto our people accumulator.
Once we’ve conjed the new person onto the people vector, we use recur to jumpback to the recursion point we defined with loop. This is analogous to therecursive call that we made in the Scala example.
If we don’t jump back, we know that we’ve gone through the sequences ofnames, and we return the people we’ve constructed.
(if (seq first-names)(recur(rest first-names)(rest last-names)(conjpeople{:first (first first-names) :last (first last-names)}))people)• Click HERE to purchase this book now. discussTail Recursion • 11

It may not be immediately apparent why the test in the if expression above
works. It’s because the seq of an empty collection is nil, which evaluates tofalse, while the seq of any other collection yields a nonempty sequence. The
snippet below demonstrates this:=> (seq [])nil=> (seq [:hi])(:hi)

Using nil as the base case for a recursion when you’re dealing with sequences
is common in Clojure.

Discussion
Tail recursion is equivalent to iteration. In fact, the Scala and Clojure compilers
will compile their respective ways of handling tail recursion down to the same
sort of bytecode that iteration in Java would. The main advantage of tailrecursion over iteration is simply that it eliminates a source of mutability inthe language, which is why it’s so popular in the functional world.
I personally prefer tail recursion over iteration for a couple of other minorreasons. The first is that it eliminates an extra index variable. The second isthat it makes it explicit exactly what data structures are being operated on
and what data structures are being generated, because they’re both passed
as arguments through the call chain.
In an iterative solution, if we were trying to operate on two sequences in lockstep and generate another data structure, they would all just be mixed inwith the body of a function that may be doing other things. I’ve found thatusing tail recursion over iteration acts as a nice forcing factor to structure
our functions well, since all of the data we’re operating on must be passed
through the call chain, and it’s hard to do that if you’ve got more than a few
pieces of data.
Since tail recursion is equivalent to iteration, it’s really a fairly low-level
operation. There’s generally some higher-level, more-declarative way to solvea problem than using tail recursion. For instance, here’s a shorter version of
the solution to our person-making example that takes advantage of somehigher-order functions in Clojure:
ClojureExamples/src/mbfpp/functional/tr/names.clj(defn shorter-make-people [first-names last-names](for [[first last] (partition 2 (interleave first-names last-names))]{:first first :last last}))• Click HERE to purchase this book now. discuss• 12Which solution to use is a matter of preference, but experienced functional
programmers tend to prefer the shorter, more-declarative solutions. They’reeasier for the experienced functional programmer to read at a glance. The
downside to these solutions is that they’re harder for the novice to grok, since
they may require knowledge of many higher-order library functions.
Whenever I’m about to write a solution that requires tail recursion, I like tocomb the API docs for higher-order functions, or a combination of higherorder functions, that do what I want. If I can’t find a higher-order functionthat works, or if the solution I come up with involves many higher-orderfunctions combined in Byzantine ways, then I fall back to tail recursion.

Related Patterns
Pattern 5, Replacing Iterator, on page ?
Pattern 13, Mutual Recursion, on page ?
Pattern 14, Filter-Map-Reduce, on page ?

• Click HERE to purchase this book now. discuss