Recursive Function Curry With JavaScript

As a disclaimer, recursive function calls in JavaScript are not particularly efficient, and you can easily exhaust the call stack.  If you are using Node.js, the default call stack size is only 984 kilobytes.  Of course, there are ways to increase the call stack size with Node.js.  These methods are hidden behind feature flags such --stack-size, which increases the memory allocation, and --harmony, which implements tail call optimization.  However, flagged features are not recommended for production.

You may be wondering why you should consider using recursion at all.  Frankly, recursive algorithms are easier to read and understand.  Recursion requires us to trade computation efficiency for human intelligibility.  Dang!

That said, the trade is fair.  To quote Donald Knuth, “premature optimization is the root of all evil.”  Code is written for computers, but it is maintained by humans (for now, at least).  Why should we sacrifice readability for performance unless we need to?

The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming.

Donald Knuth – Computer Programming as an Art (1974)

The good news is that a recursive algorithm can always be replaced with an iterative loop algorithm.  This means that we can start with a recursive, and replace it with an iterative loop later if we find that our recursive is not feasible for the problem we are solving.  With this lengthy disclaimer behind us, let’s take a look at how recursives can make a complicated problem easy to comprehend.

Using a contrived hello world example, here is how we can print “Hello world!” to the console N number of times using an iterative algorithm.

let n = 5
let i
for (i = 0; i < n; i++) {
  console.log('Hello world!')
}

If you are familiar with loop structures, there is no doubt in your mind what this code does.  It will print “Hello world!” to the console five times.  Loops seems to be a part of every introduction to programming text.  If they were not, a snippet of code like this would not be very meaningful.  The for loop structure takes three seemingly non-congruent concepts (i is zero, i is less than n, and i++) and turns them into an action that repeats N number of times.

On the flip side, a recursive algorithm is simply an algorithm that calls itself until a condition is met.

let recursiveHello = (n) => {
  if (n <= 1) {
    return
  }
  console.log('Hello Word!')
  recursiveHello(n - 1)
}

Though trivial, the code above is easy to reason with.  The function takes n.  If n is less than or equal to one, the function returns.  Otherwise, it prints “Hello World!” and then calls itself, subtracting one from n.  Unlike the iterative example, the recursive solution defines it’s own implementation.  We don’t need to know in advance how a loop works.

Let’s say that we didn’t just need to print “Hello world!” N times.  Assume that we need to repeat a given function N times.  An iterative solution might look something like what is shown below.

let iterativeRepeat = (f, n) => {
  let n = n
  let i
  for (i = 0; i < n; i++) {
    f()
  }
}

Once again, it is hard to prevent our past experiences from biasing our judgement here.  We know what this function does because we know what a loop does, even if we don’t know exactly how a loop works.  If you lacked this experience, this function would not be meaningful.

Moreover, this function is not particularly composable.  For example, we must always give this function another function to execute, and a number that tells it how many time to execute a given function.  What if we want to be able to tell our function what to execute, and the tell it how many times to execute at another point in our code.  We can’t do this with our iterative example, but we can do this with a recursive curry.

let repeat = (f) => {
  return (n) => {
    f()
    let exit = () => { return }
    return (n <= 1) ? exit() : repeat(f)(n - 1)
  }
}

At this point you might be thinking “Hey, this isn’t any less verbose than the iterative example!”  I acknowledge that, but consider this, the implementation details of the example above are contained entirely within our function.  Simply put, repeat is a function that accepts a function and returns an inner function which accepts a number.  The inner function calls the function passed to the outer function, defines an exit function, and then if exit condition is met, the exit function is called, otherwise repeat calls itself and subtracts one from n.  In addition, we are not confined to spelling out the function we want to repeat and the number of times it should be repeated every time we want to use our function.  We can leverage partial application thanks to the curried inner function.

let helloWorld = () => {
  console.log('Hello world!')
}

// call both the inner and outer functions
repeat(helloWorld)(5)

// partially apply the outer function
let sayHello = repeat(helloWorld)

// call the inner function
sayHello(5)

As you can see, we are now have a flexible and composable API were all of the implementation details are defined within the functions themselves.  We don’t have to repeat ourselves as much thanks to the ability to partially apply our function to another function.  Most importantly,  it is easy to understand and easy to use.  If we find that we are exhausting the stack, we always have the option of removing the recursive call and replacing it with an iterative loop.  Some might say that we should have started with an iterative loop, but I personally iteratives to be mentally taxing and tedious to type.  For what it is worth, even with the limitations of our call stack, sayHello() can be called 15660 times in Node.js without exhausting the stack.  Of course, this pales in comparison to how many time we can do this with an iterative algorithm, which will allow us to call the helloWorld function somewhere north of a million times.  However, it doesn’t seem likely that we will need to print “Hello world!'” a million times, so the optimization is premature.