Рекурсию можно заменить циклом

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

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

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

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

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 the exact value of the n! * if n <= 170 it will be approximate float value * if n >= 170 it will return Infinity */ factorial(n) { if (n <= 1) return 1 // TODO: Implement for non-trivial cases

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

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

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

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

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. Так как задачи будут храниться в стеке, то задачи мы будем класть в обратном порядке.

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; }

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

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:

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

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

const helloParser = * (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’], ] */

Рекурсия

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

many1(parser) { return * (text) { // Вызовем вспомогательную функцию с дополнительными параметрами yield* recMany1(parser, text, []); }; } // Принимает на вход // – парсер // – текст, на котором нужно выполнить алгоритм // – последовательность предыдущих значений * 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]; } }

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

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

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

many1(parser) { return * (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?

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

Дополнительно

Кто заметил, что это реализация стека вручную – зрят в корень.
Если кому интересен нерекурсивный алгоритм обохода дерева в ширину и в глубину, смотрите в этой ветке.

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

Источник

Возьмем какую-нибудь несложную задачку, которую можно реализовать двумя способами: с помощью цикла и с помощью рекурсии.

Тривиальная задача сравнения метода вычисления факториал с помощью цикла и метода вычисления факториала с помощью рекурсии. Берется некоторое число n, для которого вычисляем факториал разными способами.

Вычисления засовываем в цикл с 1000 итераций, чтобы снизить погрешность.

Засекаем время с помощью метода Milliseconds() (библиотека Utils). Выводим результаты. В большинстве случаев рекурсия выполняется быстрее.

[ Язык реализации: Pascal ]

Полный код

Предлагаю обсудить в комментариях, почему так происходит?

Код можно также переписать на C/C++. Об этом я уже писал в одной из первых статей:

Время работы алгоритма простого поиска элемента в массиве. Время работы кода на C++

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

Рекурсия

Рекурсией в программировании называется метод, вызывающий сам себя. Несмотря на простоту определения, этот подход достаточно сложен для понимания, поскольку человеку не свойственен подобный стиль мышления. Более того, существуют рекурсии разных типов, что вносит еще большую путаницу. Чаще всего применяются рекурсии следующих двух типов:

Головная рекурсия- рекурсивный вызов выполняется ближе к началу метода и является одним из первых обрабатываемых объектов. Поскольку он вызывает сам себя, ему приходится полагаться на результаты предыдущей операции, помещенной в стек вызовов. Из-за использования стека вызовов существует вероятность переполнения стека, если стек вызовов недостаточно велик.
Концевая рекурсия- рекурсивный вызов выполняется в конце и является последней строкой обрабатываемого кода. Этот метод не использует стек вызовов независимо от глубины рекурсии.

В математике рекурсия распространена достаточно широко, поэтому проще будет объяснить ее на примере рекурсивного вызова. Выражение 5! (факториал числа 5) можно записать следующим способом:

5 * 4!

5 * 4 * 3!

5 * 4 * 3 * 2!

5 * 4 * 3 * 2 * 1!

5 * 4 * 3 * 2 * 1

Приведен пример вычисления 5! с помощью головной рекурсии. Пример на Java

Каждый рекурсивный вызов должен быть завершен и помещен в стек вызовов до расчета факториала. Например, Java будет интерпретировать каждый вызов метода getFactorial следующим образом (каждая строка представляет объект, находящийся в стеке вызовов):

Как этот алгоритм головной рекурсии интерпретирует компилятор

Теперь приведем код для реализации концевой рекурсии

Пример вычисления 5! с помощью концевой рекурсии

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

Как этот алгоритм концевой рекурсии интерпретирует компилятор

Цикл

Языки программирования предоставляют циклы нескольких разных типов, очень хорошо знакомых большинству программистов. В языке Pascal существуют for, while и repeat циклы. В языке программирования Java и других С-подобных ЯП имеются циклы for, do и while.

Цикл – это многократное исполнение нескольких операторов. Циклы не заносят данные в стек вызовов независимо от числа исполнений цикла. Важным отличием циклов от рекурсивных функций является тот факт, что циклы используют для подсчета числа исполнений итератор, а рекурсивные функции для определения момента выхода должны выполнять сравнение результатов. Другим важным отличием является возможность применения в циклах фильтров и прочих селекторов. Примером такой ситуации может служить цикл foreach.

Что лучше?

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

Области применения рекурсии

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

Заключение

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

Спасибо, что дочитали до конца 🙂 Если вам нравятся такие разборы, и вы хотите видеть их чаще, то оставьте обратную связь (лайки, комментарии, ваши мысли).

Еще много полезного и интересного вы сможете найти на ресурсах:

Репетитор IT mentor в VK

Репетитор IT mentor в Instagram

Physics.Math.Code (Дзен)

Physics.Math.Code в контакте (VK)

Physics.Math.Code в telegram

Physics.Math.Code в YouTube

Источник

правила раздела Алгоритмы

1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.

2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.

3. Приводимые фрагменты исходного кода старайтесь выделять тегами code…/code

4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет

5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии “срочно надо”, заданный в 2003 году)

6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке 🙂

Замена рекурсии итерацией и наоборот

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

Рекурсия:

int fac(int i) {

if(i == 0) return 1;

else return i*fac(i-1);

}

Итерация:

int fac(int i) {

int c = i;

int accum;

while(c>0) {

accum*=c;

–c;

}

return accum;

}

:whistle:

Сообщение отредактировано: Мяут – 12.03.05, 04:42

Для такой простой функции это понятно, я бы вообще не стал писать факториал рекурсивно.

Я же спросил про функцию общего вида.

Мяут, как обычно, все перепутал 😆 😆

Senior Member

Рейтинг (т): 56

Ручками это делается. Ручками. Просто математики, которые исследовли ламбда-исчисление показали именно этот факт: любой итерационный процесс может быть заменен на рекурсивный и наоборот. Это доказано математикой, но рецепта нет и вряд ли будет. Если кратко – ищи теорему Стефена Клини и почитай о теории вычислимости функций(ключевые слова: Тьюринг, Гедель)

Я тебе могу накидать ссылочек по ламбда-исчислению и теории категорий. Совсем забыл сказать: ламбда-исчисление(автор – А. Черч) лежит в основе функциональных языков. Так там вместо циклов используется рекурcия.

В основе всего сейчас лежит машина Тьюринга(надеюсь, понятие об этом имеешь). Доказал эквивалентность введенного тобой исчисления машние Тьюринга – значит на твоем языке можно записать все, что записано математиками(пример – язык BrainFuck – чисто теоретически на нем можно написать программу, эквивалетную любой программе на языке, напр, С++). Далее вводится понятие вычислимой функции – то есть такой функции, для которой можно построить машину Тьюринга. А теорема С.Клини устанавливает факт соотвествия вычислимой функции и набора примитивно-рекурсивных. Вот так вот.

Цитата mikv @ 08.03.05, 07:36

Я тебе могу накидать ссылочек по ламбда-исчислению и теории категорий.

Накидай ссылочки plz.

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

Senior Member

Рейтинг (т): 47

ЗЫ… До таких высот в познании я пока еще не дошел 😀

Мы люди приземленные, итерационные методы это как грится наше все.

Вот интересно как метод Ньютона поиска корня уравнения свести к рекурсии :b: ?

Или термин итерация обозначенный выше отличается от того, что в методе Ньютона?

Или, возможно, только сходящийся итерационный процесc сводим к рекурсии? Или может быть эшшо какие ограничения должны выполняться?

Сообщение отредактировано: Math – 08.03.05, 14:28

математик

Рейтинг (т): 50

но судя по всему универсальный метод перехода не интересен. или не существует. Я думаю второе.

Цитата Math @ 08.03.05, 13:36

Вот интересно как метод Ньютона поиска корня уравнения свести к рекурсии

что за метод? Опиши плз, тогда мож и рекурсию намутим :rolleyes:

Senior Member

Рейтинг (т): 47

F(X) = 0

F(X*+Delta_X) = F(X*) + DF/DX*Delta_X + … = 0

Итерационный процесс

DF/DX(X_i)*Delta_X_i = – F(X_i)

X_i+1 = X_i + Delta_X_i

Критерий останова итерационного процесса (один, либо несколько)

1. || Delta_X_i || < eps

2. || F(X_i+1) || < eps

3. || Delta_X_i || < eps*|| X_i ||

3. || Delta_X_i || < C*eps*|| X_i – X_0 ||

5. || F(X_i+1) – F(X_i) || < eps

6. || F(X_i+1) – F(X_i) || < eps*|| F(X_i) ||

7. i == NMAX 🙂

Критерий сходимости тут чушь была написана (в Ньютоне похитрее будет)

Сообщение отредактировано: Math – 09.03.05, 09:29

Junior

Рейтинг (т): 3

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

Цитата borisvolfson @ 08.03.05, 16:42

так как такие алгоритмы зачастую работают быстрее

Почему?

Member

Рейтинг (т): 4

а в чем проблема???

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

например…

void FFF(int X)

{

[переменные]

[код A]

if (…+X < …) FFF(ZZZ);

[код B]

}

void AnalogFFF(int X)

{

[переменные][MAX];//массив наборов переменных

int __X[MAX];

int N_Iter = 1;

__X[N_Iter] = X;

while(N_Iter)

{

[код A]

if (…+__X[N_Iter] < …)

{

N_Iter++;

__X[N_Iter] = ZZZ[N_Iter-1];

continue;

}

[код B]

N_Iter–;

}

Senior Member

Рейтинг (т): 56

Цитата Guest, 08.03.2005, 15:26:25, 636544

Все верно. Ссылочки я тебе завтра подкину.

Вот основы ламбда-исчисления:

URL https://www.math.tsu.ru/books/pdf/2.pdf

Поищи еще книжку Яблонского – “Введение в дискретную математику”.

Senior Member

Рейтинг (т): 47

Ау… Люди, на мой вопрос кто-нибудь ответит? Как итерацию с критерием (возможно несходящуюся вовсе) заменить рекурсией?

Возможно в проблеме принципиальной замены рекурсии итерацией и наоборот (ВСЕГДА) имеет значение конечность числа итераций (рекурсии)? Тогда вопросов нет.

Кстати коль заговорили о заменах. Интересно в методе трассировки лучей можно рекурсию заменить на итерацию. Это очень заманчиво, т.к. уж больно тормозной метод. Хотя подозреваю это потребует эмпирического ограничения числа вложенности рекурсии.

Senior Member

Рейтинг (т): 56

Цитата Math, 09.03.2005, 13:55:58, 637816

Интересно в методе трассировки лучей можно рекурсию заменить на итерацию. Это очень заманчиво, т.к. уж больно тормозной метод. Хотя подозреваю это потребует эмпирического ограничения числа вложенности рекурсии.

ЭЭЭ. Ну делаешь цикл типа:

repeat

until вклад_луча<eps.

А вот как обсчет внутри цикла сделать.. Ты думаешь, что народ не хочет получать изображения с офигенным качеством? Видимо, нам с тобой – простым смертным это не дано понять – как можно уйти от рекурсивной трассировки лучей. Кстати, Math. Ты посылку-то получил? А то я про нее ажно забыл.

Цитата Math, 09.03.2005, 13:55:58, 637816

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

Junior

Рейтинг (т): 3

Итерацию заменить рекурсией немного сложнее, но тоже можно: условие выхода из цикла вставляем в начало рекурсивной процедуры, если оно выполняется, то выходим. Хотя этот меотд не самый универсальный. Есть интересное упражнение на этот счет: найти в массиве максимум, при помощи рекурсивной процедуры.

математик

Рейтинг (т): 50

Итерационая программа рекурсивна по определению ибо рекурсивная программа вызывает себя от 0 дл К раз.

так что тут все чисто

Senior Member

Рейтинг (т): 47

Оооо… Хорошо сказано 🙂 Я теперь кажись понял. Только вот смысл заменять итерацию рекурсией не пойму.

Senior Member

Рейтинг (т): 23

интересно, а обход дерева можно заменить циклами? Кто подскажет?

математик

Рейтинг (т): 50

Цитата uj @ 09.03.05, 15:13

интересно, а обход дерева можно заменить циклами? Кто подскажет?

может быть ответ на этот вопрос кроется в теореме – что любая существующая программа реализуема на машине Тьюринга, а в М.Т. нет рекурсии

Senior Member

Рейтинг (т): 23

не, ну на примере бы…

Добавлено 09.03.05, 16:56

в принципе, если мы имеем право говорить об упорядоченности детей у узла, тогда решение имеет место быть без всяких стеков 😆 А если нет — то хз как без стека обойтись, разве что хранить в узлах какие-то спецтеги (типа “количество_обработанных_детей”)…

Сообщение отредактировано: uj – 09.03.05, 16:57

Цитата uj @ 09.03.05, 16:45

в принципе, если мы имеем право говорить об упорядоченности детей у узла, тогда решение имеет место быть без всяких стеков А если нет — то хз как без стека обойтись, разве что хранить в узлах какие-то спецтеги (типа “количество_обработанных_детей”)…

Можно и без стека, с помощью FIFO очереди 😀 :lool:

Senior Member

Рейтинг (т): 23

Цитата Mixxx @ 09.03.05, 20:35

Можно и без стека, с помощью FIFO очереди

нельзя.

математик

Рейтинг (т): 50

Цитата uj @ 10.03.05, 04:33

Цитата Mixxx @ 09.03.05, 20:35

Можно и без стека, с помощью FIFO очереди

нельзя.

Вот пожалуйста, можно обойти граф иттеративно, используя случайное блуждание и рекурсия тут не нужна

Цитата mo3r @ 09.03.05, 03:49

Цитата borisvolfson @ 08.03.05, 16:42

так как такие алгоритмы зачастую работают быстрее

Почему?

Полагаю из-за сокращения вызовов процедур.

Senior Member

Рейтинг (т): 23

Цитата esperanto @ 10.03.05, 06:44

используя случайное блуждание

какое-какое блуждание? можно поподробней? 🙂 Я вообще предполагал аналог рекурсивного спуска по узлам. Со стеком, в котором хранятся количества обработанных детей, это делается просто. Более того, если реализацией предусмотрен порядок детей у узла, то можно обойтись и без стека. А что такое “случайное блуждание”, мы не знаем %))

математик

Рейтинг (т): 50

Цитата uj @ 10.03.05, 12:04

Цитата esperanto @ 10.03.05, 06:44

используя случайное блуждание

Ок.

Пусть нам дан ненаправленый связный граф из п вершин. Мы хотим обойти все его вершины.

Один из алгоритмов такой%

for i=1 to n^3 {

выбери случайно(равновероятно) одного из соседей вершины в которой ты находишся и иди в него

}

вот в общем то и весь алгоритм.

достоинства:

1)очень прост в реализации.

2)требует памяти всего лишь log(n) бит.

недостатки

имеются

рекурсию не использует.

Цитата mikv @ 08.03.05, 07:36

В основе всего сейчас лежит машина Тьюринга(надеюсь, понятие об этом имеешь).

Понятие имею. Но что такое рекурсия на машине Тьюринга?

Senior Member

Рейтинг (т): 23

хм. ну в двух словах все равно не понятно, где бы почитать про это? А разве мы не имеем возможности попасть на одни и те же узлы не один раз, а некоторые — совсем пропустить?

Цитата esperanto @ 10.03.05, 12:34

2)требует памяти всего лишь log(n) бит.

этого вообще не понял, сорри :wub:

Цитата uj @ 09.03.05, 15:13

интересно, а обход дерева можно заменить циклами? Кто подскажет?

Я писал такую программу без рекурсии – с использованием стека.

0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)

0 пользователей:

[ Script execution : 0,0487 ] [ 15 queries used ] [ Generated: 5.06.21, 22:26 GMT ]

Источник