Recursion

A Simple Example

Recursive functions are functions that call themselves. Recursive algorithms are generally used when the data is self-similar at different scales. Trees, linked lists, and sequences are often processed with recursive algorithms.

When writing a recursive function, , you are breaking the entire problem down step by step until the remaining problem is simple enough to solve directly. This simple solution is normally known as the terminating condition or the base case. Then, the solution can be built up from the base case to full solution.

Here is a simple example, reversing an array.

var rev = function(arrToReverse) {
    if(arrToReverse.length === 1) {
        return arrToReverse;
        } else {
            return rev(arrToReverse.slice(1)).concat(arrToReverse[0]);
        }
    }

So, rev([1, 2, 3]) => [3, 2, 1].

How does this work. Well, the base case is an array of length 1. In this case, the function just returns its argument, since the reverse of a single element array is just the array. So here, the problem has been broken down to something that can easily be solved, the reverse of a single element array. If the array is longer than one element, the function calls itself on with the array without the first element (arrToReverse.slice(1)), appends the first element (arrToReverse), and returns that value. Note that Array.push does not work here because it mutates the array and returns the number of elements in the mutated array, and we need a function that returns a new array with the element appended. Array.concat is that function.

Here is another way to look at it:

rev([1,2,3]
   rev([2,3])
      rev([3])
      return [3]
   return [3,2]
return [3,2,1]

So, at each recursive step, we are reversing a smaller array until the array length is 1. At that point, we return the single element array. At each subsequent return step, the array grows by one until the last return where we return the entire reversed array.

Iteration can be implemented as recursion

Thing of iteration as enumerating a sequence and passing it repeatedly to a function, one function call for each value in the sequence. Here is some code:

var looper = function(start, end, body) {
    if(start > end)
        return end;
    else {
        body(start);
        return looper(start+1, end, body)
        }
    }

This implements the typical for loop where a numeric iteration variable is incremented by one each time through the loop.

looper(1,3, x=>console.log(x)) => 1 2 3

Looking at the code, the if statement terminates the loop (there is not a recursive call in the true branch). If the loop is not terminating, the function is called recursively with the next element in the sequence as the start value. So the base case is start > end. Since loops are typically used for side effects, looper returns the end value, a fairly useless return value that is like many others in JavaScript.

Recursion in Tree Structures

var myObject = {abc: 1,
                def: 2,
                ghi: {
                    a: 1,
                    b: 2,
                    c: {
                       "first": 1,
                       "second" :2
                       },
                    d:3
                    },
                jkl: 3,
                mno: 4
                }


var getKeys = function(obj) {
    return Object.keys(obj).reduce((acc, key) => (typeof(obj[key]) === 'object') && (!Array.isArray(obj[key])) ?
                                   acc.concat(key, getKeys(obj[key])) : acc.concat(key), [] );
}

Here is the problem - you need to enumerate the keys in a JavaScript object. There is a nice function to do that - Object.keys(). So, call Object.keys(myObject) to get [ ‘abc’, ‘def’, ‘ghi’, ‘jkl’, ‘mno’ ]. Oops, what happened to a, b, c, d, first, and second. Well Object.keys() only enumerates keys an the top level object, not on nested objects. Nested objects can be represented by trees, like this: img

So here, we have a tree of variable arity (each node can have a different number of children), like the DOM. To enumerate all the keys, we need to walk the tree. Looking at the getKeys function, it enumerates the keys at the current level using Object.keys(obj). This returns an array of the keys in the top level object. We then reduce the array to go across all the keys. The base case is when the type of the entry is not an object - (typeof(obj[key]) = ‘object’) && (!Array.isArray(obj[key])) is false. The second part of the conditional is needed becouse typeof(array) => ‘object’. So in this case, we just concat the key into the accumulator - the array holding all the keys. If it is an object, we recurse and concatenate the result of the recursive call (an array) to the accumulator. This results in an array with all the keys at this level and all the keys at the lower level.

Drawbacks

Recursion is a very flexible way to process data structures. The downside of recursion is that every recursive call incurs function call overhead, including a stack frame. Since the stack ususally has a finite maximum size, a function with deep recursive calls can generate an exception by blowing the stack. Many languages with functional features can optimize certain types of recursive calls (tail recursion) eliminating these problems. Here is more information on tail call optimization.

Exploring Om.next Part 1

At the 2014 clojure/conj, the very first talk was about data driven applications, both back end and front end. I decided to explore clojurescript, Om and the data driven application idea by building a simple front end application in Om. It was really interesting, and I realized the claims about the flexibility and ease of development claims for data driven appplications were true. Om was interesting, and I found I liked the React model. On the other hand, there were some issues with Om. The syntax was somewhat difficult and obscure, as was the handling of cursors.

Getting Started with Emacs Org-Mode

A long time ago, in a galaxy far, far away, I was an emacs user. We had an internal version of emacs written by Warren Montgomery. It was small, and fast. It didn’t have the vi mode issues that drove me crazy in vi. I loved it. Warren’s emacs didn’t have things like elisp, but it was good for editing C code, writing nroff documents, and all the miscellaneous things in text files. Around two years ago, I got interested in clojure. I was trying to format a PDF booklet for printing, and it contained a lot of complex tables. I was usinng Ruby and Prawn. Unfortunately, prawn wasn’t up to the task and the fix looked hard. Since I was working on a deadline, I needed to look for a different solution, and I had heard about clojure and had some lisp background. I discovered that I could do most of what I needed with clj-pdf, and I could extend it a little to do the rest. I found that I really liked clojure, so I joined The Den of Clojure . I rediscovered emacs, at least a little.