A practical use for recursion

The topic of recursion is a favourite of some technical interviews and introductory computer science text books. Mathematical functions such as the Fibonacci sequence and Factorials are often used to described how it can be used, but how often does anyone use these in practice?

In this post I will illustrate a practical use for the technique and by doing so hopefully demonstrate the power it has to offer.

Simple introduction to recursion

Recursion is simply when a function calls itself which is obviously not without hazard. Usually each call is issued with different arguments that eventually limit the depth of execution.

If permitted to execute too deeply resources can become exhausted and if the execution environment does not impose a limit itself a stack overflow error will usually occur.

Take the following fragment of code,

function echo(count = 1) {
    console.log(`echo ${count++}`);
    echo(count);
}

echo();

If executed using node.js you will most likely find the count tops-out at around 8000 cycles as the environment call stack is limited.

When using recursion it is wise to consider what condition will terminate the call sequence and care should be taken to ensure the routes are well understood.

The textbox example "Fibonacci sequence"

The Fibonacci sequence is calculated from the sum of previous two calculated values.

Thus, the first Fibonacci number F(1) is 0 + 1 = 1. For convenience when n of F(n) is less than 2 we assume F(n) to be 1.

The 2nd Fibonacci number F(2) = F(1) + F(0) = 1 + 1 = 2
F(3) = F(2) + F(1) = 1 + 2 = 3
F(4) = 2 + 3 = 5 and so on.

In other words, F(n) = F(n - 1) + F(n - 2).

In code this can be captured as:

function fibonacci(n) {
    return n < 2 ? 1 : fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(1));    // 1
console.log(fibonacci(2));    // 2
console.log(fibonacci(3));    // 3
console.log(fibonacci(4));    // 5

In fact in the above example we are employing a double-recursion, for each call of fibonacci, there are (potentially) two further calls of the same function.

fibonacci(4) =>

  fibonacci(3) + fibonacci(2) =>

    fibonacci(2) + fibonacci(1) + fibonacci(1) + 1 =>

      fibonacci(1) + 1 + 1 + 1 + 1 =>

        1 + 1 + 1 + 1 + 1 = 5

So how can this be useful?

Let's take a short pause to consider the Array sort method using the following test data.

const testData = [
   {surname: 'Smith', forename: 'John'},
   {surname: 'Eich', forename: 'Brendan'},
   {surname: 'Smith', forename: 'Jane'},
   {surname: 'Crockford', forename: 'Douglas'},
   {surname: 'Berners-Lee', forename: 'Tim'}
];

Let's create a function to sort the data by the 'surname' property

function sortData(data, prop) {
    data.sort((a, b) => (a[prop] < b[prop] ? -1 : 1));
}

sortData(testData, 'surname');

console.table(testData);

and use console.table to present the results.

┌─────────┬───────────────┬───────────┐
│ (index) │    surname    │ forename  │
├─────────┼───────────────┼───────────┤
│    0    │ 'Berners-Lee' │   'Tim'   │
│    1    │  'Crockford'  │ 'Douglas' │
│    2    │    'Eich'     │ 'Brendan' │
│    3    │    'Smith'    │  'John'   │
│    4    │    'Smith'    │  'Jane'   │
└─────────┴───────────────┴───────────┘

Notice how the names are in alphabetical order by surname as intended but Jane and John Smith are not in the order. We could invert the evaluation to (a[prop] > b[prop] ? 1 : -1) but this is not really addressing the issue. A better way is to use the third valid value for the sort method (a[prop] > b[prop] ? 1 : a[prop] < b[prop] ? -1 : 0) to maintain stability of the data order. Then apply a second sort order using the forename property to determine the order when the surnames are the same.

function sortData(data, prop1, prop2) {
    data.sort((a, b) => 
        (a[prop1] > b[prop1] ? 1 : a[prop1] < b[prop1] ? -1 : 
        (a[prop2] > b[prop2] ? 1 : a[prop2] < b[prop2] ? -1 : 0)));
}

sortData(testData, 'surname', 'forename');

So, how can we make this approach more adaptable to use however many properties we want to sort by?

Next step, we will replace the two individual properties for an array using the rest operator.

function sortData(data, ...props) {
    data.sort((a, b) =>
        a[props[0]] > b[props[0]]
        ? 1 : a[props[0]] < b[props[0]] 
            ? -1 : a[props[1]] > b[props[1]]
        ? 1 : a[props[1]] < b[props[1]] ? -1 : 0
    );
}

But the code still expects there to be two property names in the array (props) so let us bring in recursion to help us.

function sortData(data, ...props) {
    data.sort(_sort(...props));

    function _sort(prop, ...props) {
        console.log(`${prop}, [${props}]`);

        const secondarySort = props.length 
            ? _sort(...props) : () => 0;
        return (a, b) => a[prop] > b[prop] 
            ? 1 : a[prop] < b[prop] 
            ? -1 : secondarySort(a, b);
    }
}

During execution the _sort function will be called twice in succession. The first call by the sortData function reports (via the console.log) the values 'surname', ['forename']. The second call is made by the _sort function itself and yields 'forename', []. The there are no more calls because the array or property names is exhausted and a zero is returned.

As long as the property name exists in the object array it can be added as another argument to the initial call and the function does not need to be adjusted, it will just issue another call. Why not true extending the example for yourself.

Conclusion

Using recursion can appear complicated and care needs to be taken to avoid a stack overflow error but the benefits can include more efficient and adaptable code and often simpler code to maintain.