The Blackstag BlogLogin
 Feeds RSS About  Categories: Everything  Hardware  Software  Programming  Finance  
Clojure Guide Chapter #16: Basic Iteration & Recursion
Posted Jun 27, 2011 [category: Programming tag: Clojure]  Parent-Post  Leave-Comment  View-Comments  

Iteration and recursion are different concepts yet they are also quite similar to each other. An iterator is a function that's used to step through a collection of items while doing operations at each step along the way and recursion is to run an operation that references itself. So as you can see these ideas are quite different from each other. The question one might ask then is how are they actually similar? Well they are similar in that recursion can be a method used to iterate over a sequence of items and Clojure also has iterators that do in fact behave recursively. This section will show how each of the concepts work and the benefits of using these varying approaches.

The FizzBuzz Challenge
Let's look at an example problem which will require the use of iteration for a solution. This particular one is also known as the FizzBuzz challenge: Write a program that prints the numbers from 1 to 100. But for multiples of three print "Fizz" instead of the number and for the multiples of five print "Buzz". For numbers which are multiples of both three and five print "FizzBuzz". So let's solve it.
The Multiple function

As you can see, for numbers 1 to 100 we need to determine if the number is a multiple of the above noted values, 3 and/or 5. In order to accomplish this we are going to use Clojure's built in modulus function named 'mod', however as you will see, the modulus function does not exactly answer our "is it a multiple?" question. What we really need to know is if the modulus is a zero indicating the first number evenly divides into the second number, therefore actually being an exact multiple. So let's build our new function named 'multiple?' to do exactly that:

=>(defn multiple? [n div] (= 0 (mod n div))) #'user/multiple =>(multiple? 3 3) true =>(multiple? 4 3) false =>(multiple? 5 3) false =>(multiple? 6 3) true
The FizzBuzz Operation

Now that we have the multiple function ready to go, let's write the FizzBuzz operation. In the Clojure world there are numerous ways to iterate through items. For FizzBuzz we are going to use 'doseq' which will do, pretty much, what it claims to. It does something for each item in a sequence of items. The first argument we will pass into doseq needs to be a vector containing a variable name (we'll use "i") which is required to bind the current item to, as the operation steps through the full sequence of items (which is also contained in the vector). The second argument that doseq requires is an operation which will occur for each item in the sequence. In our case we are going to use 'cond', which will check for each of the situations (i.e. conditions) as described in the FizzBuzz problem. Each of these condition expressions will need to be passed into 'cond' along with a corresponding operation expression that will execute in the event its condition has been met. Lastly, our cond function will also be passed an :else condition which is the catch all condition, executing only if none of the other conditions succeeded.

=>(doseq [i (range 1 101)] (cond (and (multiple? i 3)(multiple? i 5)) (println "FizzBuzz") (multiple? i 3) (println "Fizz") (multiple? i 5) (println "Buzz") :else (println i))) 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz and so on....

One additional note, you may have noticed there was an order to the conditional statements which established a priority between the cases. This ensured "FizzBuzz" superseded "Fizz" and "Buzz" when more than one case could potentially succeed and shows that 'cond' only looks for the first successful case before stopping to move on to the next item in the sequence.

The for expression

Using 'for' is another approach to iteration, but as you will see it is not suitable for the FizzBuzz problem. Like doseq, 'for' requires the first argument to be a vector containing a variable name and a sequence of items for its binding, however this approach differs from doseq by having a few modifiers that can also be included. These optional modifiers allow for specific predicate style conditions to take place. Notably the :when condition can be passed in followed by a predicate function, which stipulates whether the body should execute for the current item in the sequence. In the below example we will iterate through numbers 1 to 100 and if the number is even the body expression will evaluate with its result being added to a collection which will be returned after full completion:

=>(for [i (range 1 101) :when (even? i)] i) (2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100)

Now suppose that we don't know what numbers or how many of them are going to be passed in, yet whatever the case, we only want the first 10 even numbers returned:

=>(defn take-evens [x nums] (take x (for [n nums :when (even? n)] n))) #'user/take-evens =>(take-evens 10 (range 1 101)) (2 4 6 8 10 12 14 16 18 20)
The loop expression

A 'loop' is a commonly used facility in many languages and is sought after by many whom anticipate finding an easy to use iterator. However in Clojure the 'loop' is actually recursive therefore requiring a little more knowledge and code.

Here's the FizzBuzz challenge using the loop iterator: (loop [data (range 1 101)] (if (not (empty? data)) (let [n (first data)] (cond (and (multiple? n 3)(multiple? n 5)) (println "FizzBuzz") (multiple? n 3) (println "Fizz") (multiple? n 5) (println "Buzz") :else (println n)) (recur (rest data)))))

Much of the code here is the same as found in our doseq version, but since a loop is recursive we end up having to manually split out the first item from our sequence of items then pass that value into our 'cond' operation. We also need to include a 'recur' statement that allows the loop to re-run itself on the remaining items. Notice that in our recur statement we pass in an argument containing the remaining items in by using the 'rest' function. This new argument containing the remaining items effectively substitutes the original argument that our loop was initially given (originally containing the full sequence of items). As you can see our loop version is not well suited to solve the FizzBuzz challenge when compared to our original doseq version as we gain no benefit and end up having code that's more complicated to maintain. Now, let's take a look at using a loop expression to solve our second problem where we iterate through a sequence of numbers and collect only the first 10 that are even. Again our new loop expression will be required to split out the first item then recursively operate on the remaining items. Unlike our previous loop we will need to structure the function so that we can maintain additional arguments as the function recurs upon itself. For example a count argument will be required to track how many evens have been found and a 'result' argument will be needed to accumulate them:

(loop [data (range 1 101) n (first data) n-count 0 result nil] (if (and n (< n-count 10)) (if (even? n) (recur (rest data) (first data) (inc n-count) (cons n result)) (recur (rest data) (first data) n-count result)) (reverse result)))
Building a recursive function

We can still do better. We can take our last solution one step further by defining a recursive function that forgoes using 'loop' all together. Not only does the following function accomplish everything our previous loop had, but it also incorporates some minor modifications that make our new solution more generic and re-usable.

=>(defn take-evens ([x nums](take-evens x nums 0 nil)) ([x nums n-count result] (if (empty? nums) (reverse result) (if (< n-count x) (let [n (first nums)] (if (even? n) (recur x (rest nums) (inc n-count) (cons n result)) (recur x (rest nums) n-count result))) (reverse result))))) #'user/take-evens =>(take-evens 10 (range 1 101)) (2 4 6 8 10 12 14 16 18 20) =>(take-evens 5 (range 1 101)) (2 4 6 8 10)
Like This Post!
Chapter Links
Comments
 Comment posted on Jun 30, 2011 12:54 PM by  Bob Oberst
Here is "FizzBuzz" in VB.NET for comparison:

Private Sub FizzBuzz()
    Dim listFB As New List(Of String)
    For i As Integer = 1 To 100
        listFB.Add(Switch(i Mod 15 = 0, "FizzBuzz",
                          i Mod 3 = 0, "Fizz",
                          i Mod 5 = 0, "Buzz",
                          True,  i.ToString()))
    Next
    MessageBox.Show(String.Join(" ", listFB.ToArray()))
End Sub
Sorry, I just couldn't resist.

Bob O.
  Reply posted on Jul 01, 2011 3:39 PM by  foo
Similar solution, in Perl -- using the ternary operator instead of switch:

for my $i (1..100) {
   push @n, $i % 15 == 0 ? "FizBuzz
          : $i % 3 == 0 ? "Fizz"
          : $i % 5 == 0 ? "Buzz"
          : $i;
}

print join( " ", @n );
  Reply posted on Jul 02, 2011 8:51 AM by  Tim Robinson
Thanks for the comparisons.

And so that others also know: to format code in these comments, one needs to surround the code with special markings. For example:

@% my code %@

Translates into:

 my code 
You can also check out the link practice markup as a playground to test with.
 Comment posted on Jul 02, 2011 6:34 AM by  Dewald Troskie
And a similar solution in C# using a ternary operator

        private static void FizzBuzz()
        {
            for (var i = 1; i <= 100; i++)
            {
                var j = i % 15 == 0 ? "FizzBuzz"  : (i % 3 == 0 ? "Fizz"
                        : (i % 5 == 0 ? "Buzz"  : i.ToString()));
                Console.WriteLine(j);
            }
        }
            Console.WriteLine(string.Join(" ", listFizzBuzz.ToArray()));
        }
  Reply posted on Jul 02, 2011 6:48 AM by  Dewald Troskie
My previous example had clutter:

        private static void FizzBuzz()
        {
            for (var i = 1; i <= 100; i++)
            {
                var j = i % 15 == 0 ? "FizzBuzz"  : (i % 3 == 0 ? "Fizz"
                      : (i % 5 == 0 ? "Buzz" : i.ToString()));
                Console.WriteLine(j);
            }
        }
 Comment posted on Jul 27, 2011 10:25 PM by  newbnumber1
I'm totally a clojure newbie here, but doesn't 'for' generate a lazy sequence? Why would it "iterate through all the items" as you say?
  Reply posted on Jul 28, 2011 6:37 AM by  Tim Robinson
You're are correct. I've deleted that specific example from the post as to make sure others are not confused as well. To prove your point - one way to show that 'for' does not always iterate through all the items would be to pass in an infinite range of numbers to the take-evens function.

=>(take-evens 10 (range))
(0 2 4 6 8 10 12 14 16 18)
Had the entire infinite sequence '(range)' been evaluated a StackOverflowError would have occurred fairly quickly.

Thanks for pointing this out.
 Comment posted on Nov 01, 2011 12:40 AM by  JP
I do often wonder what the av. function heap size is and how it would compare to other interesting functional clingos like Erlang; or even the equivalent cost for a procedure call in C. Probably does not matter a great deal. Thankfully Clojure mitigates this anyway, may it be worth noting....

The loop is a non-stack consuming recursive construct.
 (loop [...] ((if (....) (....) (recur ....)))) 
Recursive function calls do nibble on your memory.
"To spare a (factorial x) demonstration,.. dare you underestimate a memory limitation"
 Comment posted on Nov 01, 2011 12:58 AM by  JP
N.B. the above comment applies to the  (recur...)  approach of recursivness for loops and functions.
The stack would only be consumed if the function actually calls itself
 Comment posted on Sep 27, 2012 10:31 PM by  Atul
Dear Tim,
     Thanks for the wonderful content... Am a Clojure newbie - am trying out the examples given here - and loving Clojure...
      One question about the example above...

 (if (and n (< n-count 10))

What does just checking n mean (first part of the and expression)...

Is it like C/C++ where n == 0 is false?
  Reply posted on Sep 28, 2012 3:48 PM by  Tim Robinson
In this case (and n ...) is checking that n exists. Here I hard coded the input data (range 1 101) and only look for the first 10 so n will always exist and it's a waste, but I think I was just testing the function by passing in various input ranges and had I passed in say (range 1 5) then on the 6th iteration (rest data) would result in 'nil' and the next checks would blow up. At least this way, when n is nil, the function stops checking and returns the results.

Good catch and great question!
Would you like to leave a comment ?
Name (required):
Website (optional, creates link to name):
email address (private & optional, used for Gravatar):
Comment (required):
 (or Practice Markup Here)
Created by Blackstag Software Inc.Copyright Tim Robinson http://blackstag.com