Algorithms: Recursive to iterative via sliding window

If a recursive algorithm depends on N previous values then one technique for converting to a tail-recursive version that evolves a iterative process is to hold a sliding window of N values and use those as the state variables to iteratively calculate the next value in the window until we reach the desired position.

When the naive implementation of this type of recursive algorithm isn't performant enough (e.g. evolves a tree recursive process and so hits stack overflow for some arguments) then this can be a quick win.

Pattern

For a recursive function foo that depends on N previous values, create an iterative function foo_iter that instead holds a sliding window of the N previous values, and repeatedly calculate next:

const foo = (n) => // something involving foo(n-N) up to foo(n-1)

// Track final position with `m`, previous values with `a`-`d` etc.
// a-d default to base case values for first N positions
const foo_iter = (n, m=(N-1), a=0, b=1, c=2, d=3, etc.) =>
    if (target position) return one of a-d
    else foo_iter(n, m+1, b, c, d, (m+1)th value)

Example: Depends on 1 previous value

If foo n should calculate the sum of integers to n then (ignoring the analytic solution) a naive recursive solution would be:

const foo = (n) =>
  n === 0 ? 0
    : foo(n - 1) + n

So holding a sliding window of 1 item, starting from base case, we can switch to iterative:

const foo_iter = (n, m=0, acc=0) =>
  n === m ? acc
    : foo_iter(n, m + 1, acc + m)

Example: Depends on 2 previous values

If fib n should calculate the sum of previous 2 values (nth Fibonacci number):

const fib = (n) =>
  n === 0 ? 0
    : n === 1 ? 1
      : fib(n - 2) + fib(n - 1)

So holding a sliding window of 2 items, starting from base cases, we can switch to iterative:

const fib_iter = (n, m = (2 - 1), a = 0, b = 1) =>
  n === m - 1 ? a
    : n === m - 0 ? b
      : fib_iter(n, m + 1, b, a + b)

Example: Depends on 4 previous values

If bar n should calculate the sum of the preceding 4 values:

const prev4 = (n) =>
  n === 0 ? 0
    : n === 1 ? 1
      : n === 2 ? 1
        : n === 3 ? 2
          : prev4(n - 4) + prev4(n - 3)
          + prev4(n - 2) + prev4(n - 1)

So holding a sliding window of 4 items, starting from base cases, we can switch to iterative:

const prev4_iter = (n, m = (4 - 1), a = 0, b = 1, c = 1, d = 2) =>
  n === m - 3 ? a
    : n === m - 2 ? b
      : n === m - 1 ? c
        : n === m - 0 ? d
          : prev4_iter(n, m + 1, b, c, d, a + b + c + d)