16
QuickTip: Reminders about recursive functions
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.
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.
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);
}
16