How avoid stack overflow with tail and trampoline in recursion function?

Question

I write the program to pass the quiz -https://www.codewars.com/kata/53d045892578b1be8b0001c4, but it still not work with big numbres. Where is my mistake ?

function thunk(fn, n, ac) {
  return fn(n, ac);
}

function trampoline(arg) {
  // console.log(arg);
  if (typeof arg === "number") {
    return arg;
  } else {
    return trampoline(arg);
  }
}

function trampolineSum(n) {
  function _sum(n, ac) {
    if (n === 0) {
      return ac;
    } else {
      return thunk(_sum, n - 1, ac + n);
    }
  }

  return trampoline(thunk(_sum, n, 0));
}

console.log(trampolineSum(4444));
console.log(trampolineSum(44444));

Hello bob , function trampoline(arg) { // console.log(arg); if (typeof arg === "number") { return arg; } else { arg = arg() return trampoline(arg); } } still not work — Quintis
– Quintis, Commented Jun 13, 2020 at 10:15
that's not a loop. that's still recursion. and thunk isn't doing anything read the instructions: "trampoline(thunk) is a function that executes repeatedly the thunk argument until it returns a non function value. Then this last value is returned." — user120242
– user120242, Commented Jun 13, 2020 at 10:16
My favorite thing about this code challenge is that the output can literally be calculated as n(n+1)/2 and doesn't even require recursion in the first place lol — Lewis
– Lewis, Commented Jun 13, 2020 at 10:18

user120242 · Accepted Answer · 2020-06-13 10:20:50Z

1

Code is broken on purpose and missing things. Try to figure it out.
Function.prototype.bind()

thunk(fn /*, args */) is a function that receives a function and possibly some arguments to be passed to the function and returns a function. When this returned function is called, it returns the result of execute the fnfunction. In functional programming, a thunk is a deferred expression (function). Its evaluation is postponed until it's really needed.

trampoline(thunk) is a function that executes repeatedly the thunk argument until it returns a non function value. Then this last value is returned.

function thunk(fn, n, ac) {
  return ???.bind(null, n, ac);
}

const trampoline = res => {
  I_WANT_TO_LOOP (typeof res === 'function') { res = res(); }
  return res;
}

function trampolineSum(n) {
  function _sum(n, ac) {
    if (n === 0) {
      return ac;
    } else {
      return thunk(_sum, n - 1, ac + n);
    }
  }

  return trampoline(thunk(_sum, n, 0));
}

console.log(trampolineSum(4444));
console.log(trampolineSum(44444));

edited Jun 13, 2020 at 10:20

answered Jun 13, 2020 at 10:19

user120242

15.3k3 gold badges43 silver badges53 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

user120242 Over a year ago

So you can try to learn yourself and figure it out. Doesn't it become pointless if I do it for you?

Bergi Over a year ago

I think it would be cleaner if thunk constructed a closure with a function expression around the call to do than to use bind

Quintis Over a year ago

` return fn.bind(null, n, ac); } const trampoline = res => { while (typeof res === 'function') { res = res(); }

Quintis Over a year ago

It was interesting quiz )

user120242 Over a year ago

GJ, go try and see if you can do what Bergi just said too, and see what he means

|

Mulan · Accepted Answer · 2020-06-13 14:21:21Z

Here's a small adaptation of your original code -

function thunk(fn, n, ac) {
  return [ thunk, _ => fn(n, ac) ]
}

function trampoline(r) {
  while (r && r[0] === thunk)
    r = r[1]()
  return r
}

function trampolineSum(n) {
  function _sum(n, ac) {
    if (n === 0) {
      return ac;
    } else {
      return thunk(_sum, n - 1, ac + n);
    }
  }

  return trampoline(thunk(_sum, n, 0));
}

console.log(trampolineSum(4444)) // 9876790
console.log(trampolineSum(44444)) // 987656790

Consider alternate implementations -

const recur = (...v) =>
  ({ recur, [Symbol.iterator]: _ => v.values() })

const loop = f =>
{ let r = f()
  while (r && r.recur === recur)
    r = f(...r)
  return r
}

const trampolineSum = n =>
  loop
    ( (m = n, ac = 0) =>
        m === 0
          ? ac
          : recur(m - 1, ac + m)
    )

console.log(trampolineSum(4444)) // 9876790
console.log(trampolineSum(44444)) // 987656790

Collectives™ on Stack Overflow

How avoid stack overflow with tail and trampoline in recursion function?

2 Answers 2

9 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

9 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related