const ackermann1 = (m, n) => {
  if (m === 0) {
    return n + 1;
  }

  if (n === 0) {
    return ackermann1(m - 1, 1);
  }

  return ackermann1(m - 1, ackermann1(m, n - 1));
};

const ackermann2 = (m, n) => {
  const stack = []; // Стековые кадры

  let state = "initial"; // Instruction Pointer
  let value = undefined; // Возвращаемое значение рекурсивного вызова

  const call = (params, returnState) => {
    // Добавляем кадр и переходим в начало функции
    stack.push({ params, returnState });
    state = "initial";
  };

  const ret = (val) => {
    // Удаляем кадр и переходим к месту возврата
    const frame = stack.pop();
    value = val;
    state = frame.returnState;
  };

  call([m, n]);

  while (stack.length !== 0) {
    const frame = stack[stack.length - 1];
    const {
      params: [m, n],
    } = frame;

    if (state === "initial") {
      if (m === 0) {
        ret(n + 1);
        continue;
      }

      if (n === 0) {
        call([m - 1, 1], "recursive call n=0");
        continue;
      }

      call([m, n - 1], "general recursive call 1");
    } else if (state === "recursive call n=0") {
      ret(value);
    } else if (state === "general recursive call 1") {
      call([m - 1, value], "general recursive call 2");
    } else if (state === "general recursive call 2") {
      ret(value);
    }
  }

  return value;
};

const ackermann3 = recursive(function* (m, n) {
  if (m === 0) {
    return n + 1;
  }

  if (n === 0) {
    return yield [m - 1, 1];
  }

  return yield [m - 1, yield [m, n - 1]];
});

const recursive = (generator) => (...params) => {
  let generatorObj = generator(...params);

  let request = undefined; // Рекурсивный запрос от генератора
  let result = undefined; // Ответ на запрос

  const stack = [];

  while (true) {
    // Получаем IteratorResult 
    const message = generatorObj.next(result); 
    
    if (message.done) {
      // Если генератор завершил работу - передаём
      // значение выше по стеку или завершаемся, если 
      // выше никого нет  
      if (stack.length === 0) {
        return message.value;
      }

      result = message.value;
      generatorObj = stack.pop();
    } else {
      // В противном случае - сохраняем состояние в стек, 
      // создаём новый генератор и дальше работаем с ним

      result = undefined;
      request = message.value;

      stack.push(generatorObj);
      generatorObj = generator(...request);
    }
  }
};

const benchmark = (fn, params) => {
  try {
    const start = performance.now();
    fn(...params);
    const end = performance.now();
    return end - start;
  } catch (e) {
    return undefined;
  }
};

const params = [3, 10];
let fns = [
  ["ackermann1", ackermann1],
  ["ackermann2", ackermann2],
  ["ackermann3", ackermann3],
];

for (let [name, fn] of fns) {
  const samples = 100;
  let data = [];

  for (let i = 0; i < samples; i++) {
    data.push(benchmark(fn, params));
  }

  const total = data.reduce((acc, time) => acc + time, 0);
  console.log(`${name} mean: ${total/samples}ms`);
}