Recursive generator VM example

index.js

const arrayLast = arr => arr[arr.length - 1];
const { toString } = Object.prototype;
const isGenerator = val => toString.call(val) === '[object Generator]';

const cache = new Map();

function *fibonacci(n) {
  let value;

  if (cache.has(n)) return cache.get(n);

  if (n <= 1) {
    value = n;
  } else {
    const a = yield fibonacci(n - 2);
    const b = yield fibonacci(n - 1);
    value = a + b
  }

  
  yield value;

  cache.set(n, value)

  return value;
}

function *trampolineGenerators(rootFn) {
  const stack = [rootFn];

  let fn = rootFn, step = fn.next();

  while (true) {
    while (step.done) {
      // a function's control flow terminated
      stack.pop();

      fn = arrayLast(stack);

      if (!fn) {
        // the call stack is exhausted, we are done
        return step.value;
      }

      // a value is returned from a call
      step = fn.next(step.value);
    }

    if (isGenerator(step.value)) {
      // function call: generator lazily invoked another generator
      stack.push(step.value);

      fn = arrayLast(stack);
    } else {
      // generator yields a value to the caller of trampolineGenerators
      yield step.value;
    }

    step = fn.next();
  }
}

console.log([...trampolineGenerators(fibonacci(3))]);

// [ 1, 0, 1, 2 ]

// OK I admit, it's not a very good example. The numbers are all out of order! So it goes.