Recursion
Recursion, Tail Calls, Proper Tail Calls, Examples
Recursion is the process in which a function is called by itself, either directly or indirectly. Recursion allows you to write some very elegant code. But when using recursion you need to be aware of the pitfals.
Recursion example
Here is a function that will call itself a given number of times.
function factorial(n, accumulator) {
if (n === 0) {
return accumulator
}
return factorial(n — 1, n * accumulator)
}
factorial(5, 1) //==>> 120The function above will recursively call the factorial function from 5 to 0 with an accumulator value. The condition n === 0 is the break condition for this function. Every recursive function must have a break condition. Otherwise calling the function will lead to an infinite loop.
Tail Call
A tail call is a function call whose return value is used as the callers return value. In the function above return factorial(n — 1, n * accumulator) is a tail call.
In JavaScript every function call will add a call frame to the call stack. The frame is popped off the call stack when the call returns. However a recursive function does not return immediately. It will make a recursive call before it returns. This will add to the call stack every time. Recursively calling from the tail position sufficently deep, will cause the call stack to run out of space, throwing a RangeError.
Proper Tail Call
A “Proper Tail Call” is a mechanism by which the language compiler recognizes tail calls, and reuses the call frame, so that the call stack does not grow. The tail call does not need the call frame anyway, since its only job is to return the call. Proper tail calls are otherwise known as tail call optimization.
Tail call optimizations are important to functional programming languages as they are used for iteration and extreme recursion. The language Scheme uses recursion for all loop constructs, and does not have any other looping mechanism.
Does that mean we cannot use recursion in JavaScript? The answer is no. We can, but we need to use it carefully. For the call stack to throw a RangeError we need to recurse to a depth of more than 10000. We can safely use recursion when we know that we are in a situation that will never hit that limit. Examples are
- Iterating over nested Objects like the DOM.
- Iterating over the arguments of a function.
- ES6 specifies proper tail calls. So you can use recursion safely in future, in ES6 compliant engines.
Iterating over an Object
We will write a simple JSON stringify function using recursion.
var test = {
name: “John”,
age: 21,
scores: [89, 72, 96, 55, 66]
}function type(obj) {
return Object.prototype.toString.call(obj).match(/.* (.*)\]/)[ 1]
}function stringify(obj) { if (type(obj) === “Function”) {
return null
}
if (type(obj) === “Undefined”) {
return null
}
if (type(obj) === “Null”) {
return “null”
}
if (type(obj) === “Number”) {
return obj
}
if (type(obj) === “String”) {
return ‘”’ + obj + ‘”’
}
if (type(obj) === “Array”) {
return ‘[‘ +
obj.map(function(o) {
return stringify(o)
}).join(“,”)
+ ‘]’
}
if (type(obj) === “Object”) {
var result = []
Object.keys(obj).forEach(function(key) {
var val = stringify(obj[key])
if (val !== null) {
result.push(‘”’ + key + ‘”: ‘ + val)
}
})
return “{“ + result.join(“,”) + “}”
}
}stringify(test) //==> {“name”: “John”,”age”: 21,”scores”: [89,72,96,55,66]}
The function type returns the type of the given object as a string. Function stringify will return the corresponding stringified object based on the type. It is recursively called when the type is Array or Object. As you can see, recursion is a very elegant way to do a task.
Asynchronous calls using recursion
You can write a series of asynchronous calls without nesting them, by using recursion. Here is a function asyncSerial which takes a set of asynchrous functions as its arguments. It calls each function with a function called next. Inside the callback of the asynchronous function you must call next to trigger the next function in the series.
function asyncSerial() {
var args = Array.prototype.slice.call(arguments)
function next() {
var func = args.shift()
if (func) {
func(next)
}
}
next()
}The arguments to asyncSerial are coerced into an array called args. The function next when called will shift out the first element of args which will be a function. Then it simply calls the function with itself as the argument. next will be called inside the callback defined inside the funtion. See this in action.
The example below is a nodejs program to asynchronously copy an input file to an output file. It makes three asynchronous calls. fs.exists, fs.readFile, fs.writeFile. Of cource we could write such a program in one line of code, but the purpose of this example is show you how you can use recursion, and how you can use it solve your own problem.
var fs = require(“fs”),
infile,
outfile,
datafunction asyncSerial() {
var args = Array.prototype.slice.call(arguments)
function next() {
var func = args.shift()
if (func) {
func(next)
}
}
next()
}asyncSerial(
function(next) {
infile = process.argv[2] || “”;
fs.exists(infile, function (exists) {
if (exists) {
next();
} else {
console.log(“File does not exist: “ + this.infile)
}
})
},
function(next) {
outfile = process.argv[3]
if (outfile) {
next();
} else {
console.log(“Output File Name is Required”)
}
},
function(next) {
fs.readFile(infile, function (err, contents) {
if (err) {
console.log(“Error reading File: “ + infile)
} else {
data = contents
next()
}
})
},
function() {
fs.writeFile(outfile, data, function (err) {
if (err) {
console.log(“Error writing File: “ + outfile)
}
})
})
asyncSerial is called with four functions as its arguments. Each function is called with next. The functions in turn call next from inside their callbacks. In case of error they simple don’t call next at that point, and the program terminates.
