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:
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.