Recursive Patterns
I noticed a few naturally recurring pattern in my recursive functions.
function sum (nums, n = 0, sum = 0) {
// exit condition
if (n >= list.length) return sum
return sum(nums, n + 1, sum + nums[n])
}
When an algorithm has $O(n)$ complexity in all cases—i.e. it visits every item once—the pattern tends to be an early exit at the start with guaranteed tail-end recursion. There might also be a body of calculations in between, for more complex operations. It's important to put the early exit as a [[Guard Clause]] at the start of the function, as apposed to conditional recursion, so that the function can exit immediately if no iteration of the loop is necessary. For example,
function sum (nums, n = 0, sum = 0) {
if (n + 1 < list.length) {
return sum(nums, n + 1, sum + nums[n])
}
return sum + nums[n]
}
This code would work exactly the same, except in the case of an empty array. If nums
was empty, the function would still attempt to sum a single number, not realizing that it was not protected from an out-of-bounds exception by the previous recursion, as there was none. It is better to have each call check itself for exits, such that an empty collection still functions properly.
#software #active