Taking recursion to the next level

If you have read any articles on the topic of recursion the chances are they used either the Fibonacci Sequence or the calculation of Factorial numbers as the case study. Both of these are rather trivial and somewhat pointless examples outside of their academic purpose. However, to ease in this article we will briefly reprise the examples.

Simple examples

Factorial numbers

This must be the simplest example as it takes in, manipulates and returns a single value.

function factorial(n, fac = 1) {
    return n ? factorial(n - 1, fac * n) : fac;
}

OK, I was not quite truthful about only taking in a single value but the second value is not expected to be supplied on the initial call but provided as part of the recursive calculation, to pass the running total from one call to the next. But, why bother, the following iterative example works just as well.

function factorial(n) {
    let fac = 1;
    for (; n; n--) {
        fac *= n;
    }
    return fac;
}

Those less familiar with the concept of recursion might find the iterative approach easier to understand but that is the lesson. Familiarity with the concept and its benefits (and drawbacks) will help you understand how and when a recursive solution is beneficial. I would argue these simple examples don't go quite far enough.

Fibonacci sequence

This has to be The textbook example, yet I have included it because it is the next minor step in the learning process.

function fibonacci(n, curr = 1, prev = 0) {
    return n ? fibonacci(n - 1, curr + prev, curr) : curr;
}

As before, this function is only expected to be supplied with a single argument when called, the others are used to pass values in subsequent calls. And again, the iterative version is hardly complicated.

function fibonacci(n) {
    let curr = 1, prev = 0;
    for (; n; n--) {
        [curr, prev] = [curr + prev, curr];
    }
    return curr;
}

Neither of the examples given above demonstrate the power recursion has to offer.

Micro operations

A couple of features common to most recursive functions can be characterised as the micro and macro operations.

The micro operation (or operations) is at the core of the function and performs the primary function. In the Factorial function it is n => n * (n - 1), in the Fibonacci function it is:

1. add prev to curr
2. copy the previous curr to prev for the next cycle (which might require a temporary variable).

Macro operations

This is the mechanism by which the recursion is repeated and, more importantly, concluded. In all versions of the ‘simple examples’ we repeated the micro operation n times (while it is truthy), reducing it by one (decrementing) each cycle and terminating when n = 0, or in the context of JavaScript when n became falsy.

A more realistic example

I recall reading somewhere (citation required) that around 80% of source code is engaged in converting data from one format to another. I assume the remainder is concerned with interfacing and persistence. A common feature of the ‘simple examples’ is they have a single path (cycle) of execution but recursive functions can have more paths, as will be demonstrated in the following example.

NB: The following example has questionable utility but again serves very well as an academic exercise.

objectFlat()

Following in the mode of the Array.flat method, objectFlat is intended to reduce the level of property nesting of a given dataset.

The function makes the following technical assumptions:

1. The input data will be a valid JSON object. By that I mean it is an object that could have resulted from a JSON.parse operation and contains no cyclic references.
2. The data types will be limited to the primitive values: null, Boolean (true, false), numbers and strings.
3. The number of supported data structures is also limited to Arrays and Objects although these can be nested, their flattening being the purpose of the function.
4. Arrays will only be flattened when they are object properties, not nested in top-level arrays.
5. Flattened array items will be converted into object properties with the name in the following format propertyName[array Item Index].
6. Likewise, flattened object properties will be renamed objectPropertyName.subPropertyName.

Should you be interested, the source code contained within this article can be found in my GitHub repo.

Yet again, the function accepts a number of arguments but only the first parameter is expected on the initial call. Subsequent calls might provide the second to indicate the returned value is for an object property. More on this in a moment.

Primitive values

The initial argument can be an array, object or a primitive data value. In the case of the latter, the value is returned unchanged. So the following four examples will be output from the function without modification (just JSON stringified to aid presentation).

Test input:

const primitiveValues = [null, true, 42, 'epsilon'];

Test results (JSON stringified):

Arrays

Arrays are only flattened when they are assigned to the property of an object, otherwise the array remains unchanged in structure. If the items in the array are objects, they will be flattened as will be demonstrated later.

Test input:

const arrayTests = [
    [],
    [null, true, 42, 'epsilon'],
    [
        [null, true, 42, 'epsilon'],
        [null, true, 42, 'epsilon'],
        [null, true, 42, 'epsilon'],
    ],
];

Test results (JSON stringified):

Objects

Nested objects are flattened. By that I mean, the properties of the inner object are renamed and copied to the outer object.

Test input:

const objectTests = [
    {},
    {
        alpha: null,
        beta: true,
        gamma: 42,
        delta: 'epsilon',
    },
    {
        zeta: {
            alpha: null,
            beta: true,
        },
        eta: {
            gamma: 42,
            delta: 'epsilon',
        },
    },
    {
        theta: {
            zeta: {
                alpha: null,
                beta: true,
            },
            eta: {
                gamma: 42,
                delta: 'epsilon',
            },
        },
    },
];

Test results (JSON stringified):

Notice how the name of the flattened object property is composed of the property path for the value but as a string. In the third example, the input property theta.eta.delta is converted to a single top-level property of the name “theta.eta.delta” in the output object.

But what happens when we combine arrays in an object or objects as elements of an array?

Test input:

const compositeTests = [
    {
        alpha: null,
        beta: true,
        gamma: 42,
        delta: 'epsilon',
        zeta: [null, true, 42, 'epsilon'],
    },
    [
        {
            alpha: null,
            beta: true,
            gamma: 42,
            delta: 'epsilon',
        },
        {
            alpha: null,
            beta: true,
            gamma: 42,
            delta: 'epsilon',
        },
    ],
];

Test results (JSON stringified):

The first test case is an object containing a property zeta that has an array value. In the output object the property zeta is replaced with a property for each item in its array, with the name of the property being a composite of the property name followed by the array item subscript as follows: zeta[0]. However, in the last test case the output remains unchanged because the array is not an object property and the objects in the array only have primitive values.

Implementation

Now for the “meat” of the article, how was the objectFlat function assembled, how does it employ recursion, what does this let us and what are some of the pit-falls of recursion?

Under the hood

The initial version of the function will present an interface (signature) with only one parameter; we will consider the second parameter later. Within the function we determine if the supplied argument is an Array, Object or a primitive value. We detect arrays using the idiomatic (built-in) isArray method of the Array prototype. There is no equivalent built-in function or method for detecting Objects and there are a mass of edge cases to trip up hand-created isObject functions, but here is what we will use.

function isObject(obj) {
    return obj === Object(obj);
}

Once we have eliminated Arrays and Objects, we only have to consider primitive values.

function objectFlat(srcObj) {
    if (Array.isArray(srcObj)) {
        return srcObj.map(item => objectFlat(item));
    }
    if (isObject(srcObj)) {
        return Object.entries(srcObj).reduce((tgtObj, [key, val]) => {
            tgtObj[key] = objectFlat(val);
            return tgtObj;
        }, {});
    }
    return srcObj;
}

Primitive values are returned immediately and unchanged. Array items and Object properties get pushed back through the objectFlat function, but also remain unchanged. Notice how we have two places where recursion happens, array items and object properties (key, value pairs). In this example the macro operation is ‘self limiting’ (as long as there are no circular references). There will be a finite number of array items and object properties. For input that is already flat the function of course achieves nothing, but that is in itself a result. However, as you might expect, the real work happens when the data is nested.

However, the above ‘initial’ function still performs some recursion, except for the primitive value test cases. The three array test cases “recurs” 0, 4 and 15 times, respectively. The first case is an empty array so no items are processed, but the second example is populated with four primitive items, so the function is recursively called for each, to one depth of stack. The third Array example is nested with another array, each with four primitive values. In this example, each sub-array results in a recursive call (3), each of which will call the function a further four times, once for each primitive item (3 x 4). Fifteen recursive calls in total.

The four object test cases perform similarly. The first is empty so there is no recursion. The second example is a flat object of four primitive values so there are four recursive calls. The third and forth examples recurs all primitive values, which results in 6 and 7 function calls to a depth of three and four levels, respectively.

So, how do we go about ‘flattening’ array items and object properties?

There are two ways to access object properties: dot-notation and bracket-notation.

const example = {
    alpha: {
        beta: true,
        gamma: 42,
        delta: [
            'epsilon',
            'zeta',
            'eta'
        ]
    }
};

In the above example we can access the gamma property as follows:

// dot notation
console.log(example.alpha.gamma); // 42

// bracket notation - literal
console.log(example['alpha']['gamma']); // 42

// bracket notation - indirect
const propName = 'gamma';
console.log(example.alpha[propName]); // 42

The property names (as strings) can include dot delimiters and square brackets, which enables us to convert nested properties and array subscripts like this.

console.log(example['alpha.gamma']); // 42

// bracket notation - literal
console.log(example['alpha.delta[1]']); // 'zeta'

However, array items can only be ‘flattened’ in this way when they are the value of an object property. Encoded properties by extending the property name is the reason why we need a second parameter, to pass the name of the property (propName) for the next call.

function objectFlat(srcObj, propName)

Converting primitives

    return propName ? { [propName]: srcObj } : srcObj;

Encoding primitive values is trivial because there is no further recursion. The function either returns the unchanged value or wraps it in an object when a property name is supplied, which can be subsumed into the object of the caller.

Converting (flattening) array items

    if (Array.isArray(srcObj)) {
        return propName
            ? srcObj.reduce(
                    (tgtObj, item, index) => ({
                        ...tgtObj,
                        [`${propName}[${index}]`]: objectFlat(item),
                    }),
                    {}
            )
            : srcObj.map(item => objectFlat(item));
    }

Likewise, when a property name is passed into a call with an array srcObj, the propertyName is encoded in conjunction with the index of each array element. The value of the array elements will themselves be encoded through a further call. The result of the call will be assigned to the value of a property in a new object, with the encoded name.

Converting (flattening) object properties

    if (isObject(srcObj)) {
        return Object.entries(srcObj).reduce((tgtObj, [key, val]) => {
            const tgtProp = propName ? `${propName}.${key}` : key;
            return { ...tgtObj, ...objectFlat(val, tgtProp) };
        }, {});
    }

When a propName is supplied we encode it into the name of each property to produce a new object that is returned. Once received from the calling location the original property, and its object value, are replaced with the properties of the object returned by the call.

In summary

When the objectFlat function is called with an object containing nested objects or arrays, the function is called again for each nested property/element, along with the name of the property of which it is the value. When nested, event primitive values are passed in a recursive call. In all cases the function returns an object that is expanded deconstructed to replace the nested property.

In total there are three places within the objectFlat function where it calls itself, twice within the array processing and a third in the object processing. However, it is only the call in the object processing that supplies a property name, which is how we flatten the object.

Proper Tail Calls and Tail Call Optimisation

One of the criticisms of recursive functions is that, if they are not written correctly, they can result in a considerable call stack. Each time a function is called, memory is allocated and memory locations (addresses) stored in a memory structure, known as a call stack, so they can be restored as each function completes.

If the function is excessively recursive or unbounded the calls can exhaust the stack resulting in what is known as a stack overflow.

Tail Call Optimisation (TCO) is a facility of the runtime environment that greatly reduces call stack proliferation by replacing the call with the result but in order to use this facility;

• recursive functions need to be written in a way they can take advantage of TCO and
• the runtime has to support the facility.

The JavaScript specification (ECMAScript ECMA-262) defines how this can be achieved but as yet (July 2023) very few JS runtimes/engines exist that have implemented the mechanism. See section 14.6 of ECMA-262 of 2015.

But even if/when the runtime supports TCO, the code has to be written in a particular way to take advantage of it. Functions need to employ Proper Tail Calls (PTC). This means function return must be either a value or a pure function call. The function cannot be dependent on anything in the function from where it is being called. This is why the examples in this post pass data from one call to the next via parameters, to ensure independence.

Additional material

1. ES6 Tail Calls
2. 2ality - tail call optimization