6. Recursion and Looping

Overview

In this chapter, you will learn more flexible ways to work with collections. When the problem you need to solve does not fit the patterns that we've looked at so far. We will also use doseq for loops with side effects and see how you can avoid writing some loops by using specialized repetition functions such as repeat and iterate. You will use recur for recursive looping and identify when this is possible, work with the loop macro, and solve complex problems with recursion.

By the end of this chapter, you will be able to implement different aspects of recursion and see how they can replace traditional loops.

Introduction

Data in our programs doesn't always take the nice, linear form for which functions such as map or reduce are particularly adapted. None of the techniques we've discussed in the last two chapters will work for traversing non-linear structures such as trees or graphs. And while it's possible to do a lot by being creative with reduce, the strong guard rails that reduce provides can sometimes get in the way of writing expressive code. There are situations that call for tools that give the programmer more control. Clojure has other resources for these kinds of problems and that is what we are going to look at in this chapter.

Recursion plays a major role when functions such as map and reduce are no longer adapted to the task at hand. Thinking recursively is an important Clojure skill to learn. Because functional programming languages tend to emphasize recursion, this might seem unfamiliar if your background is in more procedural languages. Most programming...

Clojure's Most Procedural Loop: doseq

Before we get started with recursion, let's take a look at the doseq macro. It is arguably the most procedural of Clojure's looping alternatives. At least, it looks a lot like the foreach loop found in other languages. Here's a very simple use of doseq:

user> (doseq [n (range 5)]
    (println (str "Line " n)))
Line 0
Line 1
Line 2
Line 3
Line 4
nil

Translated into English, we might say: "For each integer from 0 to 5, print out a string with the word 'Line' and the integer." You might ask: "What is that nil doing there?" Good question. doseq always returns nil. In other words, doseq doesn't collect anything. The sole purpose of doseq is to perform side effects, such as printing to the REPL, which is what println does here. The strings that appear in your REPL—Line 0, Line 1, and so on—are not returned values; they are side effects.

Note...

Solving Complex Problems with Recursion

When we talk about recursion, there are really two categories of use cases that are quite different from each other. This is particularly true of Clojure. On the one hand, recursion is the primary, low-level way to build loops where other languages would use for, foreach, or with. On the other hand, functional languages such as Clojure generally make it easier for programmers to find elegant, recursive solutions to complex problems.

Tail recursion and functions, or loops, built around recur are suited for problems where the data, input, and output, is essentially linear. Because tail recursive functions can only return one call at a time, they cannot handle problems where it is necessary to follow multiple, forking paths through the data. Clojure provides the tools you need. Using them may require some practice in approaching the problem in a recursive style.

To help build this skill, the remaining exercises in this chapter will be dedicated...

Summary

We've covered a lot of ground in this chapter. Recursion in Clojure, as in many functional languages, is a central concept. On the one hand, it can be necessary for some fairly simple looping situations. In those cases, recur, whether used with loop or in a recursive function, can almost be seen as just "Clojure's syntax for looping." Understanding tail recursion is important for avoiding mistakes, but otherwise, it is relatively simple. On the other hand, recursion can be an extremely powerful way of solving complex problems. If it makes your head spin from time to time, that's normal: recursion is more than just a technique. It's a way of thinking about problem solving. Don't worry, though. In the next chapter, you are going to be able to practice your recursion skills some more!

In the next chapter, we will continue exploring the recursive techniques and focus on lazy evaluation.