Trampoline Recursion Stack Overflow

I have this recursive function sum which computes sum of all numbers that were passed to it. It works fine if only 'few' numbers are passed to it but overflows call stack otherwis

Solution 1:

The other answer points out the limitation on number of function arguments, but I wanted to remark on your trampoline implementation. The long computation we're running may want to return a function. If you use typeof res === 'function', it's not longer possible to compute a function as a return value!

Instead, encode your trampoline variants with some sort of unique identifiers

constbounce = (f, ...args) =>
  ({ tag: bounce, f: f, args: args })

constdone = (value) =>
  ({ tag: done, value: value })

consttrampoline = t =>
{ while (t && t.tag === bounce)
    t = t.f (...t.args)
  if (t && t.tag === done)
    return t.valueelsethrowError (`unsupported trampoline type: ${t.tag}`)
}

Before we hop on, let's first get an example function to fix

const none =
  Symbol ()

constbadsum = ([ n1, n2 = none, ...rest ]) =>
  n2 === none
    ? n1
    : badsum ([ n1 + n2, ...rest ])

We'll throw a range of numbers at it to see it work

constrange = n =>
  Array.from
    ( Array (n + 1)
    , (_, n) => n
    )

console.log (range (10))
// [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]console.log (badsum (range (10)))
// 55

But can it handle the big leagues?

console.log (badsum (range (1000)))
// 500500

console.log (badsum (range (20000)))
// RangeError: Maximum call stack size exceeded

See the results in your browser so far

const none =
  Symbol ()

constbadsum = ([ n1, n2 = none, ...rest ]) =>
  n2 === none
    ? n1
    : badsum ([ n1 + n2, ...rest ])

constrange = n =>
  Array.from
    ( Array (n + 1)
    , (_, n) => n
    )

console.log (range (10))
// [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]console.log (badsum (range (1000)))
// 500500console.log (badsum (range (20000)))
// RangeError: Maximum call stack size exceeded

Somewhere between 10000 and 20000 our badsum function unsurprisingly causes a stack overflow.

Besides renaming the function to goodsum we only have to encode the return types using our trampoline's variants

constgoodsum = ([ n1, n2 = none, ...rest ]) =>
  n2 === none
    ? n1
    ? done (n1)
    : goodsum ([ n1 + n2, ...rest ])
    : bounce (goodsum, [ n1 + n2, ...rest ])

console.log (trampoline (goodsum (range (1000))))
// 500500console.log (trampoline (goodsum (range (20000))))
// 200010000// No more stack overflow!

You can see the results of this program in your browser here. Now we can see that neither recursion nor the trampoline are at fault for this program being slow. Don't worry though, we'll fix that later.

constbounce = (f, ...args) =>
  ({ tag: bounce, f: f, args: args })
  
constdone = (value) =>
  ({ tag: done, value: value })
  
consttrampoline = t =>
{ while (t && t.tag === bounce)
    t = t.f (...t.args)
  if (t && t.tag === done)
    return t.valueelsethrowError (`unsupported trampoline type: ${t.tag}`)
}

const none =
  Symbol ()

constrange = n =>
  Array.from
    ( Array (n + 1)
    , (_, n) => n
    )

constgoodsum = ([ n1, n2 = none, ...rest ]) =>
  n2 === none
    ? done (n1)
    : bounce (goodsum, [ n1 + n2, ...rest ])

console.log (trampoline (goodsum (range (1000))))
// 500500console.log (trampoline (goodsum (range (20000))))
// 200010000// No more stack overflow!

The extra call to trampoline can get annoying, and when you look at goodsum alone, it's not immediately apparent what done and bounce are doing there, unless maybe this was a very common convention in many of your programs.

We can better encode our looping intentions with a generic loop function. A loop is given a function that is recalled whenever the function calls recur. It looks like a recursive call, but really recur is constructing a value that loop handles in a stack-safe way.

The function we give to loop can have any number of parameters, and with default values. This is also convenient because we can now avoid the expensive ... destructuring and spreading by simply using an index parameter i initialized to 0. The caller of the function does not have the ability to access these variables outside of the loop call

The last advantage here is that the reader of goodsum can clearly see the loop encoding and the explicit done tag is no longer necessary. The user of the function does not need to worry about calling trampoline either as it's already taken care of for us in loop

constgoodsum = (ns = []) =>
  loop ((sum = 0, i = 0) =>
    i >= ns.length
      ? sum
      : recur (sum + ns[i], i + 1))

console.log (goodsum (range (1000)))
// 500500console.log (goodsum (range (20000)))
// 200010000console.log (goodsum (range (999999)))
// 499999500000

Here's our loop and recur pair now. This time we expand upon our { tag: ... } convention using a tagging module

constrecur = (...values) =>
  tag (recur, { values })

constloop = f =>
{ let acc = f ()
  while (is (recur, acc))
    acc = f (...acc.values)
  return acc
}

const T =
  Symbol ()

consttag = (t, x) =>
  Object.assign (x, { [T]: t })

constis = (t, x) =>
  t && x[T] === t

Run it in your browser to verify the results

const T =
  Symbol ()

consttag = (t, x) =>
  Object.assign (x, { [T]: t })

constis = (t, x) =>
  t && x[T] === t

constrecur = (...values) =>
  tag (recur, { values })

constloop = f =>
{ let acc = f ()
  while (is (recur, acc))
    acc = f (...acc.values)
  return acc
}

constrange = n =>
  Array.from
    ( Array (n + 1)
    , (_, n) => n
    )

constgoodsum = (ns = []) =>
  loop ((sum = 0, i = 0) =>
    i >= ns.length
      ? sum
      : recur (sum + ns[i], i + 1))

console.log (goodsum (range (1000)))
// 500500console.log (goodsum (range (20000)))
// 200010000console.log (goodsum (range (999999)))
// 499999500000

extra

My brain has been stuck in anamorphism gear for a few months and I was curious if it was possible to implement a stack-safe unfold using the loop function introduced above

Below, we look at an example program which generates the entire sequence of sums up to n. Think of it as showing the work to arrive at the answer for the goodsum program above. The total sum up to n is the last element in the array.

This is a good use case for unfold. We could write this using loop directly, but the point of this was to stretch the limits of unfold so here goes

constsumseq = (n = 0) =>
  unfold
    ( (loop, done, [ m, sum ]) =>
        m > n
          ? done ()
          : loop (sum, [ m + 1, sum + m ])
    , [ 1, 0 ]
    )

console.log (sumseq (10))
// [ 0,   1,   3,   6,   10,  15,  21,  28,  36, 45 ]//   +1 ↗ +2 ↗ +3 ↗ +4 ↗ +5 ↗ +6 ↗ +7 ↗ +8 ↗ +9 ↗  ...

If we used an unsafe unfold implementation, we could blow the stack

// direct recursion, stack-unsafe!constunfold = (f, initState) =>
  f ( (x, nextState) => [ x, ...unfold (f, nextState) ]
    , () => []
    , initState
    )

console.log (sumseq (20000))
// RangeError: Maximum call stack size exceeded

After playing with it a little bit, it is indeed possible to encode unfold using our stack-safe loop. Cleaning up the ... spread syntax using a push effect makes things a lot quicker too

constpush = (xs, x) =>
  (xs .push (x), xs)

constunfold = (f, init) =>
  loop ((acc = [], state = init) =>
    f ( (x, nextState) => recur (push (acc, x), nextState)
      , () => acc
      , state
      ))

With a stack-safe unfold, our sumseq function works a treat now

console.time ('sumseq')
const result = sumseq (20000)
console.timeEnd ('sumseq')

console.log (result)
// sumseq: 23 ms// [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ..., 199990000 ]

Verify the result in your browser below

constrecur = (...values) =>
  tag (recur, { values })

constloop = f =>
{ let acc = f ()
  while (is (recur, acc))
    acc = f (...acc.values)
  return acc
}

const T =
  Symbol ()

consttag = (t, x) =>
  Object.assign (x, { [T]: t })

constis = (t, x) =>
  t && x[T] === t

constpush = (xs, x) =>
  (xs .push (x), xs)

constunfold = (f, init) =>
  loop ((acc = [], state = init) =>
    f ( (x, nextState) => recur (push (acc, x), nextState)
      , () => acc
      , state
      ))

constsumseq = (n = 0) =>
  unfold
    ( (loop, done, [ m, sum ]) =>
        m > n
          ? done ()
          : loop (sum, [ m + 1, sum + m ])
    , [ 1, 0 ]
    )

console.time ('sumseq')
const result = sumseq (20000)
console.timeEnd ('sumseq')

console.log (result)
// sumseq: 23 ms// [ 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, ..., 199990000 ]

Solution 2:

Browsers have practical limits on the number of arguments a function can take

You can change the sum signature to accept an array rather than a varying number of arguments, and use destructuring to keep the syntax/readability similar to what you have. This "fixes" the stackoverflow error, but is increadibly slow :D

function_sum([num1, num2, ...nums]) { /* ... */ }

I.e.:, if you're running in to problems with maximum argument counts, your recursive/trampoline approach is probably going to be too slow to work with...