Превращаем рекурсию в цикл

Максим написал рекурсивный алгоритм, и столкнулся с Stack Overflow exception.

Зачем Максим это сделал?

Потому что он любит короткие и элегантные на его взгляд решения.

Он не наслаждается, когда пишет так:

function factorial(n) {
  let res = 1;
  for (let i = 2; i <= n; i++) {
    res *= i;
  }
  return res;
}

Он хочет писать вот так:

const factorial = (n) => (n > 1 ? n * factorial(n - 1) : 1);

Но когда он запускает подобные этому рекурсивные алгоритмы бывает так, что он видит это:

Почему «элегантный» алгоритм не сработал?

Потому что в Javascript есть ограничение на глубину стека вызовов. Каждый вложеный вызов функции factorial кладёт в стек запись о вызове функции. Когда размера стека не хватает — возникает эта ошибка. В случае на картинке — ошибка вылетела при 10700+ вложеных вызовах.

Что делать Максиму?

Зависит от правильности алгоритма, размера задачи или стойкости его принципов.

Сначала он должен проверить, не ошибся ли он в алгоритме. Большинство подобных ошибок, всё таки являются ошибкой алгоритма.

Если это не так, то нужно оценить размер задачи. Написанный рекурсивный алгоритм может быть никогда не будет применятся на данных, для обработки которых нужна такая глубина вызовов. В таких случаях оставь рекурсивный алгоритм. Возможно пометь границы применимости в комментарии к коду и достаточно.

Но так как Максим всё же встретился с этой ошибкой, то возможно ему нужно подумать над тем, чтобы заменить рекурсивный алгоритм.

Варианты замены рекурсивного алгоритма

Обычно рекурсивный алгоритм может быть заменён циклом и, если необходимо, вспомогательной структурой данных, чаще всего стеком.

В случае расчёта факториала алгоритм лучше заменить на циклический описанный выше. Но существуют более сложные рекурсивные алгоритмы, где нужно использовать дополнительную структуру данных.

Метод «TODO-списка»

Я использую такую вспомогательную аналогию для того, чтобы представить рекурсивный алгоритм в форме цикла. Я представляю выполнение алгоритма как череду выполнения задач с одновременным планированием того, что необходимо сделать далее.

Например расчёт факториала можно реализовать так:

/**
 * factorial(n) returns n! for non negative integer n
 * if n <= 18 it will be exact value of the n!
 * if n <= 170 it will be aproximate float value
 * if n >= 170 it will return Infinity
 */
function factorial(n) {
  if (n <= 1) return 1
  // TODO: Implement for non-trivial cases

Сначала написали короткую документацию к этой функции.

Потом на первой строке тела функции обработали «тривиальный» случай, когда n <= 1.

Теперь решим эту задачу для не «тривиальных» случаев.

Для этого определим стек команд и переменную для результата.

function factorial(n) {
  if (n <= 1) return 1;
  let result = 0;
  const todoStack = [];

  // TODO: Plan some tasks

  while (todoStack.length > 0) {
    const task = todoStack.pop();

    // TODO: process the task
  }

  return result;
}

Цикл while постепенно исчерпает список задач. Результат после этого будет хранится в переменной result.

Теперь нам необходимо запланировать несколько задач, которые наш алгоритм должен выполнить.

Первое что он должен сделать это вычислить факториал N - 1.

Потом он должен умножить этот факториал N - 1 на N.

Добавим эти задачи в todoStack. Так как задачи будут хранится в стеке, то задачи мы будем класть в обратном порядке.

function factorial(n) {
  if (n <= 1) return 1;

  let result = 0;
  const todoStack = [];

  todoStack.push({ type: "multiplyBy", multiplier: n });
  todoStack.push({ type: "calculteFactorial", value: n - 1 });

  while (todoStack.length > 0) {
    const task = todoStack.pop();

    // TODO: process the task
  }

  return result;
}

Теперь напишем реализацию этих команд в цикле, который исчерпывает стек задач.

function factorial(n) {
  if (n <= 1) return 1;

  let result = 0;
  const todoStack = [];

  todoStack.push({ type: "multiplyBy", multiplier: n });
  todoStack.push({ type: "calculateFactorial", value: n - 1 });

  while (todoStack.length > 0) {
    const task = todoStack.pop();

    if (task.type === "multiplyBy") {
      const { multiplier } = task;
      result *= multiplier;
      continue;
    }

    if (task.type === "calculateFactorial") {
      const { value } = task;

      // «Тривиальный» случай
      if (value <= 1) {
        result = 1;
        continue;
      }

      // Не «тривиальный», планируем новые задачи.
      todoStack.push({ type: "multiplyBy", multiplier: value });
      todoStack.push({ type: "calculateFactorial", value: value - 1 });
      continue;
    }
  }
  return result;
}

Это очень медленный алгоритм, по сравнению с циклом for. Но он демонстрирует основную идею, что есть стек «задач», и цикл, который этот стек опустошает постепенно приходя к некоторому результату.

Реальный пример более сложной рекурсии

Сергей решил занятся самообучением алгоритмам и решил написать нечто из раздела парсеров. Он решил, что парсером будет функция, которая принимает некоторый текст. И возвращает итератор по возможным результатам парсинга. Результатом парсинга является спарсеное значение и остаток строки, который не был использован при парсинге.

type Parser<T> = (
  input: string
) => Iterator<[parsedValue: T, restString: string]>;

Так вот он хочет написать такую функцию many1:

function many1<T>(parser: Parser<T>): Parser<T[]> {
  // TODO: Write this function
}

Она должна применить этот парсер один или более раз и вернуть все возможные варианты последовательных применений этого парсера.

const helloParser = function* (text) {
  if (text.startsWith("hello")) {
    yield ["hello", text.slice("hello".length)];
  }
};

const many1HelloParser = many1(helloParser);

const parsed = [...many1HelloParser("hellohellohelloabc")];

/*
parsed = [
    [['hello', 'hello', 'hello'], 'abc'],
    [['hello', 'hello'], 'helloabc'],
    [['hello'], 'hellohelloabc'],
]
*/

Рекурсия

Решим, с помощью рекурсии.

function many1(parser) {
  return function* (text) {
    // Вызовем вспомогательную функцию с дополнительными параметрами
    yield* recMany1(parser, text, []);
  };
}

// Принимает на вход
// - парсер
// - текст, на котором нужно выполнить алгоритм
// - последовательность предыдущих значений
function* recMany1(parser, text, parsedValues) {
  // итерируемся по вариантам и решаем задачу для остатка строки каждого из них
  for (const [parsed, restString] of parser(text)) {
    const newParsedValues = [...parsedValues, parsed];
    yield* recMany1(parser, restString, newParsedValues);
  }

  // Если предыдущие значения есть - то это тоже валидный результат
  if (parsedValues.length > 0) {
    yield [parsedValues, text];
  }
}

Со списком задач

Задача парсинга текста действительно может вызывать большую глубину рекурсии. Поэтому Сергею необходимо переписать этот алгоритм через цикл.

Вот как он это сделал:

function many1(parser) {
  return function* (text) {
    const tasksStack = [];

    tasksStack.push({
      type: "iterate",
      iterator: parser(text),
      parsedValues: [],
    });

    while (tasksStack.length > 0) {
      const task = tasksStack.pop();

      if (task.type === "yield") {
        // Если задача вернуть один результат - возвращаем его
        yield [task.parsedValues, task.restString];
        continue;
      }

      if (task.type === "iterate") {
        // Имеем итератор по спарсенным значениям
        // Запрашиваем вариант парсинга
        const step = task.iterator.next();

        // Если нельзя спарсить ничего. То нечего и делать
        if (step.done) continue;

        // Получилось спарсить
        const [parsedValue, restString] = step.value;

        // Запланируем следующие задачи:
        // 1. Решить исходную задачу для restString
        // 2. Продолжить решать итерацию текущей задачи
        // 3. Выдать текущий результат как валидный результат

        // 3
        tasksStack.push({
          type: "yield",
          parsedValues: [...task.parsedValues, parsedValue],
          restString,
        });

        // 2
        tasksStack.push(task);

        // 1
        tasksStack.push({
          type: "iterate",
          iterator: parser(restString),
          parsedValues: [...task.parsedValues, parsedValue],
        });
      }
    }
  };
}

Схема точно такая как для факториала: стек задач, и цикл, который их исчерпывает.

Здесь используется стек для хранения двух видов задач:

• выдать один результат
• получить вариант парсинга из итератора и решить задачу для остатка строки и потом вернуть промежуточный результат

Послесловие

Я поделился своими аналогиями, которые могли бы применить абстрактные «Максим» или «Сергей» для того чтобы превратить рекурсию в цикл.

Расскажите, как вы превращаете рекурсию в циклы. Возможно у вас есть свои аналогии? Или может вам они не нужны? Возможно вы бы решили задачу Сергея по другому, расскажите как? Попадались ли вам рекурсивные алгоритмы в ваших проектах? Были ли случаи, где встречали Stack Overflow Error?

Очень интересно узнать ваш опыт и ваше мнение особенно по задаче парсинга. Можно ли её решить без рекурсии, но более просто?