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