DEV Community

Matt Kenefick
Matt Kenefick

Posted on

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);
}
Enter fullscreen mode Exit fullscreen mode

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

  1. This function should stop because the input array is empty.
  2. This function will reach that goal because I'm continually shrinking an array by popping it.
  3. This function manages state through the output parameter.
  4. 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');
Enter fullscreen mode Exit fullscreen mode

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);
}
Enter fullscreen mode Exit fullscreen mode

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Explore a sea of insights with this enlightening post, highly esteemed within the nurturing DEV Community. Coders of all stripes are invited to participate and contribute to our shared knowledge.

Expressing gratitude with a simple "thank you" can make a big impact. Leave your thanks in the comments!

On DEV, exchanging ideas smooths our way and strengthens our community bonds. Found this useful? A quick note of thanks to the author can mean a lot.

Okay