QuickTip: Reminders about recursive functions

Recursive functions call themselves repeatedly until there is a reason to stop.

Before writing your function, you should start out with a few considerations:

First: "What is the reason this function should stop?"

Second: "How does this function work toward that goal?"

Third: "How does this function manage state?"

Last: "What are my defaults for malformed data?"

Let's take this basic sum function as an example:

function sum(input: number[] = [], output: number = 0): number {
    if (!input || input.length === 0) {
        return output;
    }

    output += input.pop();

    return sum(input, output);
}

In the function above, the answers to our questions are:

This function should stop because the input array is empty.

This function will reach that goal because I'm continually shrinking an array by popping it.

This function manages state through the output parameter.

This function defaults output to 0, and returns default upon malformed data.

After writing the signature for your function, you should first work on the logic that will exit the recursion. It's almost like a logic-sandwich in the fact that the top layer is where you exit and the bottom layer is where you continue the recursion. The middle can be whatever you want it to be.

For your top layer, you should check for success or failure (e.g. malformed data). This could include a null value being passed in, an incorrect type, an array reaching zero length, an integer exceeding a certain value, etc. If the conditions are met, this is where you return output; and exit your recursion.

For your bottom layer, you continue the recursion by calling your function again. It's important to think about this question: "What has changed since the last time this function was called?" Are you incrementing an index? Are you popping an array? If something doesn't change, the function will continue forever (unless you add a limit/killswitch).

For the middle, you can do whatever you want here, but it must include logic to reach your goal of exiting recursion ("What should make this function stop?"). Maybe you're concatenating strings, or making calls to a database, or something else. In our example above, we are continually running .pop() on an array that will eventually reach 0 in length.

CAUTION! Be careful about areas where you might accidentally counter your own logic. For instance:

const value = input.pop();
...
input.push('lorem ipsum');

In the above example, I'm popping the last value every time, but I'm also adding a value meaning the length of the array will never reach 0 and eventually causes a stack overflow.

Additional considerations:

Would my function benefit from a limit/killswitch?

For testing, and on potentially dangerous code, it might be valuable to add a killswitch of sorts that ends recursion after X executions.

It usually involves an independent iterator to ensure that no matter what happens in the code, after i > 999 this function will stop.

If you've ever run a DELETE or UPDATE query in SQL and saw 1,604,201 rows affected, then you'll understand the benefit of this.

I generally build in a killswitch when I'm writing a complicated recursive function to prevent stack overflows and then remove it once I'm satisfied with my logic.

Would my function benefit from an iterator?

Iterator values are an easy way of managing how many times a function has been called; it can be used for array positions, linear time, and more.

This is typically handled by accepting an index parameter and incrementing it on each recursion. See the example below:

function recursion(index = 0, max = 10) {
    // Top layer determines why we exit
    if (index >= max) {
        return index;
    }

    // Middle layer inches us toward our exit
    index++;

    // Bottom layer continues our recursion
    return recursion(index, max);
}