Recursive Optimization through Bare Operation

• Eliminate recursive call stack consumption
• Modularize and abstract recurrence-based defintion
• Implicitly memoize

Usage

First-order recurrences

Factorial

robo: <T>({ base: T[], recurrence: ((results: T[], cases?: number[]) => T) }) => T

const factorial = robo<number>({
  base: [1],
  recurrence: ([subcase], [n]) => n * subcase
})

• call stack space: O(1)
• global space: O(1)
• runtime: O(n)

Performance comparison

	Non-tail recursive	Tail recursive (without TCO)	robo
call stack space	O(n)	O(n)	O(1)
global space	O(1)	O(1)	O(1)
runtime	O(n)	O(n)	O(n)

---

Higher-order recurrences

Fibonacci

robo: <T>({ base: T[], recurrence: ((results: T[], cases?: number[]) => T) }) => T

const fibonacci = robo<number>({
  base: [0, 1],
  recurrence: ([subcase0, subcase1]) => subcase0 + subcase1
  // recurrence: sum
})

• call stack space: O(1)
• global space: O(1)
• runtime: O(n)

Performance comparison

	Non-tail recursive	Tail recursive (without TCO)	robo
call stack space	O(n)	O(n)	O(1)
global space	O(1)	O(1)	O(1)
runtime	O(2n)	O(n)	O(n)

---

Derangements

robo: <T>({ base: T[], recurrence: ((results: T[], cases?: number[]) => T) }) => T

const numDerangements = robo<number, number>({
  base: [1, 0],
  recurrence: ([subcase0, subcase1], [previous]) =>
    previous * (subcase0 + subcase1)
})

• runtime: O(n)
• call stack space: O(1)
• global space: O(1)

Performance comparison

	Non-tail recursive	Tail recursive (without TCO)	robo
call stack space	O(n)	O(n)	O(1)
global space	O(1)	O(1)	O(1)
runtime	O(2n)	O(n)	O(n)

---

List-based recurrences

Subsets

robo: <T, Element>({ base: T[], recurrence: ((results: T[], cases?: Element[]) => T) }) => T

const subsets = roboList<number[][], number>({
  base: [[[]]],
  recurrence: ([subsets], [element]) => [
    ...subsets,
    ...subsets.map(subset => [...subset, element])
  ]
})

• call stack space: O(1)
• global space: O(2ⁿ)

Performance comparison

	Recursive	robo
call stack space	O(elements.length)	O(1)
global space	O(2n)	O(2n)

---

General recurrences: next functions, base functions and memoize

Binomial coefficient

robo: <T, Case>({
  base: (c: Case) => T,
  next: (c: Case) => Case[],
  recurrence: ((results: T[], cases?: Case[]) => T)
  memoize: boolean | (c: Case) => string | number
}) => T

type Choose = {
  n: number
  k: number
}

const binomialCoefficient = robo<number, Choose>({
  base: ({ n, k }) => {
    if (k === 0) return 1
    if (n === k) return 1
  },
  next: ({ n, k }) => [{ n: n - 1, k: k - 1 }, { n, k: k - 1 }],
  recurrence: sum,
  memoize: true
})

• call stack space: O(1)
• global space: O(k)
• runtime: O(nk)

Make change

robo: <T, Case>({
  base: (c: Case) => T,
  next: (c: Case) => Case[],
  recurrence: ((results: T[], cases?: Case[]) => T)
  memoize: boolean | (c: Case) => string | number
}) => T

interface Change {
  coins: number[]
  target: number
}

const makeChange = robo<number, Change>({
  base: ({ coins, target }) => {
    if (!coins.length) return 0
    if (target && !coins.length) return 0
    if (!target) return 1
  },
  next: ({ coins, target }) => [
    { coins, target: target - coins[0] },
    { coins: coins.slice(1), target }
  ],
  recurrence: sum,
  memoize: ({ coins, target }) => [coins.length, target]
})

• call stack space: O(1)
• global space: O(Max(coins.length, target))
• runtime: O(coins.length * target)

---

Unbounded recurrence parameters: tuplicity

Powers of twc: complete induction recurrence

Powers of two satisfy the following mathematical equation:

2 ⁿ - 1 = 2⁰ + ... + 2^{n - 1}

From this we get the following (inefficient) recurrence where the number of used subcases is unbounded (scales with the input):

powerOfTwo(n) = powerOfTwo(0) + ... + powerOfTwo(n - 1)

powerOfTwo(0) = 1

For a recurrence function with a paramater that is unbounded in size, this must be specified by assigning the optional tuplicity parameter to Infinity:

// Inefficient recurrence for powers of two

const powerOfTwo = robo<number, number>({
  tuplicity: Infinity,
  base: [1],
  recurrence: cases => sum(cases) + 1
})

• call stack space: O(1)
• global space: O(n)
• runtime: O(n²)

Performance comparison

	Non-tail recursive	Tail recursive (without TCO)	robo
call stack space	O(n)	O(n)	O(1)
global space	O(1)	O(1)	O(1)
runtime	O(n!)	O(n)	O(n)

---

Bounded recurrence parameters: tuplicity

Specify constant recurrence parameters size with tuplicity parameter for space optimizations:

const binaryTreeSearch = <T>(target: T) =>
  robo<Root<T>, Root<T>>({
    tuplicity: 2,
    base: node => {
      if (node.value === target) return node
      if (!node) return null
    },
    recurrence: ([left, right]) => left || right,
    next: node => [node.left, node.right]
})

or by representing next with an array

const binaryTreeSearch = <T>(target: T) =>
  robo<Root<T>, Root<T>>({
    base: node => {
      if (node.value === target) return node
      if (!node) return null
    },
    recurrence: ([left, right]) => left || right,
    next: [node => node.left, node => node.right]
})