Three mundane things you can do with recursion

← back to the blog

I have been spending some quality time with Clojure, not because I think I'm likely to use it for a real project any time soon, but because both the syntax and behaviour of the language are so different from what I'm used to that I feel like a total n00b again. This is uncomfortable, but it's a good thing: I'm looking at my even my production code in a whole new way.

Recursion is a tricky concept, but it's so ubiquitous in Clojure that you have to get used to it really, really fast. Clojure does not have formal loop structures, and people who are used to functional languages in fact argue that loops are really a tacky add-on to imperative languages.

While recursion often feels like it's performing some sort of magic (see merge sort, or any algorithm that walks through tree-like data) it can also have some mundane uses. Sometime practising with the mundane is more illustrative.

This post is intended for those who have some experience with programming but who are unfamiliar or somewhat familiar with recursion. It is mostly conceptual but will include some example in JavaScript. I will also include one example in Clojure as it was the place I got started in thinking about all this. Strict familiarity with either language is not a requirement.

1. Basic looping

One personal kata of mine is writing a function that prints out the Fibonacci series. Here's how it works:

The first two numbers in the series are 1 and 1. After that, each number is the sum of the two numbers that came before it. So the third Fibonacci number is 2 (1 + 1), then 3 (1 + 2), then 5 (2 + 3) and we get:

1, 1, 2, 3, 5, 8, 13, 21

and so on.

The Fibonacci series is the basis of such diverse concepts as the golden mean and the rhythmic structure of progressive metal band Tool's masterpiece "Lateralus". It's simple enough to code with a loop, but in Clojure, we can't use a loop. Here's what I came up with:

(defn fibonacci
    ([max sofar]
        (def nextnum (+ (first (rseq sofar)) (second (rseq sofar))))
        (if (< nextnum max)
            (fibonacci max (conj sofar nextnum))
                sofar))
        ([max]
                (fibonacci max [1, 1])))

The same thing in JavaScript:

function makeFibonacci(soFar) {
    var next;
    if (!soFar || soFar.length < 2) {
        soFar = [1, 1];
    }
    next = soFar[soFar.length - 2] + soFar[soFar.length - 1];
    if (next > 1000) {
        return soFar;
    } else {
        soFar.push(next);
        return makeFibonacci(soFar);
    }
}

In both cases, we're starting by defining a default (1, 1) in case that hasn't been done yet. We generate the next number in the series by adding the last two, then pop it on the end of the array. Then we recur (recur in Clojure and calling the function itself in JavaScript) and continue the cycle.

One final, really important point: we have an exit strategy. Once the next number is over 1000, we cop out. The real Fibonacci series continues forever, but of course we can't do this in a computer program. Unlike an ordinary loop, however, a recursive loop has to keep track of all of the whole list of calling functions (the call stack), and will eventually just run out of memory. This is the dreaded "stack overflow" error.

Looping through a list

Libraries such as Underscore.js contain powerful methods that allow you to transform arrays and objects according to arbitrary functions. Suppose you have an array of numbers, and you want a new array containing the square of each one. You could do this with a loop, but this is prone to errors-of-one and mushes the looping logic together with the transforming logic. An alternative is to use Underscore's .map:

_.map([1, 2, 3, 4], function(item) {
    return item * item;
});
// returns [1, 4, 9, 16]

While the actual Underscore function just uses a loop, let's implement our own version of using recursion.

function myArrayMap(inputArray, f) {
    var outputArray = [];
    function recur(inputArray) {
        if (inputArray.length === 0) {
            return outputArray;
        }
        var head = inputArray[0];
        var tail = inputArray.slice(1);
        outputArray.push(f(head));
        return recur(tail);
    }
    return recur(inputArray);
}

This shows a useful pattern: wrapping the recurring function in an outer function which sets standard arguments and defines the things the recurring function will need.

Ignoring the first if block for now, the inner recurring function splits the input array into a head (one item) and a tail (the rest) and performs the user-defined function f on the head. It pushes the new value onto the output array, then calls itself with the tail (now one item shorter than the input array). As before, there is a bottom-out point: when the input array is empty (zero items in length) we just return the output array.

Setting default arguments

Suppose you are creating a function to initialize a jQuery carousel on the element of your choice. You can pass a selector string as an argument, or you can call the function without arguments and will use the default .carousel selector. There are a number of ways to set a default argument, but one that isn't obvious is the simply call the function itself with the default argument in place.

function initCarousel(selector) {
    if (!selector) {
        initCarousel('.carousel');
    }
    $(selector).carousel();
}

This pattern is especially mundane and not common in JavaScript, but one place something similar is done is in ensuring that constructor functions are called correctly. In JavaScript, calling a function that is intended to be used as a constructor without new does not cause a fatal error, but can cause really confusing and unexpected results. This can be guarded against like so:

function MyConstructor(args) {
    if (!(this instanceof MyConstructor)) {
         return new MyConstructor(args);
    }
    // create object here
}

If we ever forget to call MyConstructor with new (setting this to the function that is currently executing), the function will simply check itself and fix our mistake. Pretty neat!

Conclusion

Recursion is usually trotted out a solution to complicated problems, but there are also simple cases where it can be useful. I hope this tutorial has let you see it in a new way!