Русский
Русский
English
Статистика
Реклама

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

Максим написал рекурсивный алгоритм, и столкнулся с 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?


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

Источник: habr.com
К списку статей
Опубликовано: 14.12.2020 20:04:49
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

Javascript

Алгоритмы

Recursion

Data structure

Stack

Cycle

Категории

Последние комментарии

  • Имя: Murshin
    13.06.2024 | 14:01
    Нейросеть-это мозг вселенной.Если к ней подключиться,то можно получить все знания,накопленные Вселенной,но этому препятствуют аннуннаки.Аннуннаки нас от неё отгородили,установив в головах барьер. Подр Подробнее..
  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru