Рекурсия: различия между версиями
Содержимое удалено Содержимое добавлено
м вычитка, много правок |
|||
Строка 1:
[[w:Рекурсия|Рекурсия]] — это жемчужина [[w:
Простота рекурсии обманчива. Метод рекурсии таит в себе много опасностей и сложностей, и в то же время готовит много приятных сюрпризов.
Давно известен такой математический приём, как разбиение задачи на простые шаги, каждый из которых тоже можно разложить на более мелкие шаги и так далее, пока не доберёмся до самых элементарных «шажочков».
Представим, что нужно пройти 1000 шагов. Для решения делаем один шаг, остаётся 999: задача упростилась. Сделав такое упрощение 999 раз, дойдём до самой элементарной задачи — шагнуть один раз. Конечно, этот пример
Вы, наверное, уже заметили сходство понятий рекурсии и [[w:
== Числа Фибоначчи ==
Рассмотрим последовательность чисел <math>1, 1, 2, 3, 5, 8, 13, 21, \dots</math> в которой каждое число является суммой двух предыдущих. Это [[w:Числа Фибоначчи|числа Фибоначчи]]. Формальное их определение таково:
:<math>F(1) = 1</math>, <math>F(2) = 1</math>, <math>F(n) = F(n - 2) + F(n - 1)</math>, если <math>n > 2</math>.
Функция <math>F(n)</math> задана ''рекурсивно'', то есть «через себя». База — значения функции <math>F</math> на аргументах 1 и 2, а шаг — формула <math>F(n) = F(n - 2) + F(n - 1)</math>.
Современные языки программирования дают возможность программировать рекурсивные определения без особых усилий, но в таких определениях таятся опасности.
== Проблемы рекурсии и как их решать ==
При вычислении значения <math>F(6)</math> будут вызваны процедуры вычисления <math>F(5)</math> и <math>F(4)</math>. В свою очередь, для вычисления последних потребуется вычисление двух пар <math>F(4)</math>, <math>F(3)</math> и <math>F(3)</math>, <math>F(2)</math>. Можно нарисовать «дерево рекурсивных вызовов».
Строка 29 ⟶ 28 :
[[Изображение:treerecurs.jpg]]
Можно заметить, что <math>F(3)</math>
Есть способ решить проблему повторных вычислений. Он очевиден —
[[Изображение:fibtree2.jpg]]
Например, рекурсивный алгоритм вычисления чисел Фибоначчи легко дополнить тремя «строчками»:
# создать глобальный массив <math>FD</math>, состоящий из нулей;
# после вычисления числа Фибоначчи <math>F(n)</math> поместить его значение в <math>FD[n]</math>;
# в начале рекурсивной процедуры сделать проверку на то, что <math>FD[n] = 0</math> и, если <math>FD[n] \ne 0</math>, то вернуть <math>FD[n]</math> в качестве результата, а иначе приступить к рекурсивному вычислению <math>F(n)</math>.
Такая ''рекурсия с запоминанием'' называется ''динамическим программированием сверху''.
Рекурсию с запоминанием для вычисления чисел Фибоначчи мы привели просто для демонстрации идеи. Для чисел Фибоначчи есть простой «человеческий алгоритм», не использующий рекурсивные вызовы и запоминание всех вычисленных значений. Достаточно помнить два последних числа Фибоначчи, чтобы вычислить следующее. Затем предпредыдущее можно «забыть» и перейти к вычислению следующего:
# <math>a = b = 1</math>;
# если <math>n > 2</math>, то сделать <math>n - 2</math> раз: <math>c= a + b</math>; <math>a = b</math>; <math>b = c</math>;
# вернуть ответ <math>b</math>;
Этот алгоритм ''линейный'' по <math>n</math>, то есть для вычисления <math>n</math>-го числа Фибоначчи требуется <math>n</math> шагов. Но здесь есть важная тонкость: число знаков в числе Фибоначчи растёт с <math>n</math>, соответственно, время выполнения операции сложения <
<math>F(n) = \frac{1}{\sqrt Конечно, пока числа не выходят за пределы машинной точности (на компьютерах с 32-битной архитектурой это означает «меньше <math>2^{32}</math>»), сложение выполняется за фиксированое число тактов. Но, начиная с <math>F(48)</math>, уже нельзя использовать Указанный пошаговый алгоритм вычисления чисел Фибоначчи с учётом затрат на сложения длинных чисел является квадатичным по <math>n</math> (при увеличении <math>n</math> в <math>k</math> раз время вычисления <math>F(n)</math> увеличивается в <math>k^2</math> раз), а не линейным
Особенно просто и наглядно функцию вычисления чисел Фибоначчи можно задать на языке [[w:Mathematica|Mathematica]] (см. http://www.wolfram.com):
Если определить числа Фибоначии первым способом, то время вычисления <math>F[40]</math> будет более минуты. Если же использовать второе определение, то 209-значное число <math>F[1000]</math> будет вычисленно практически мгновенно, хотя, безусловно, и второй способ далеко не самый оптимальный.
=== Задача 1 ===
Покажите, что в дереве рекурсивных вызовов рекурсивной функции вычисления числа Фибоначчи <math>F(n)</math> присутствует <math>F(n - 1)</math> вызовов <math>F(2)</math> и <math>F(n - 2)</math> вызовов <math>F(1)</math>. В частности при вычислении <math>F(6)</math> в дереве присутствуют 5 вызовов <math>F(2)</math> и 3 вызова <math>F(1)</math>.
=== Задача 2 ===
Покажите, что рекурсивный алгоритм вычисления числа Фибоначчи <math>F(n)</math> требует времени пропорционального <math>F(n)</math>.
=== Задача 3 ===
Найдите две геометрические прогрессии с различными ненулевыми значениями разности <math>\lambda</math>, удовлетворяющие соотношению <math>b_n = b_{n - 1} + b_{n - 2}</math>. Покажите, что сумма этих прогрессий также удовлетворяет этому соотношению. Представьте <math>F(n)</math> в виде суммы двух геометрических прогрессий, а именно, найдите <math>C_1</math>, <math>C_2</math>, <math>\lambda_1</math>, <math>\lambda_2</math> такие, что <math>F(n) = C_1 \cdot \lambda_1^n + C_2 \cdot \lambda_2^n
=== Задача 4 ===
Напишите рекурсивную процедуру вычисления чисел Фибоначчи, основанную на рекуррентных формулах: <math>F(2n) = 2F(n + 1)F(n)- F(n)^2</math>
== Задача о золотой горе ==
На международной олимпиаде по информатике в 1994 году
[[Изображение:goldenmount.jpg]]
'''Формулировка задачи''': На рисунке
# Каждый шаг может идти диагонально вниз направо или диагонально вниз налево.
# Количество строк в треугольнике
# Числа в треугольнике все целые от 0 до 99 включительно.
В примере, описанном выше, это путь 7, 3, 8, 7, 5, дающий максимальную сумму
; Входные данные
; Выходные данные
В примере, описанном выше, это путь 7, 3, 8, 7, 5, дающий максимальную сумму 30.
Пример входных данных:
5
7
8 1 0
2 7 4 4 Эту задачу можно встретить и под названием «Золотая гора» — нужно спуститься с горы и собрать как можно больше золота.
Можно заметить, что в любом месте горы начинается гора меньшего размера, будем называть такие горы ''горками''. Пусть число <math>a(i, j)</math> есть число в треугольнике, находящееся в <math>i</math>-й строчке на <math>j</math>-м
[[Изображение: triangles.jpg]]
На рисунке обозначены две горки (треугольники): одна с вершиной в числе
Решить эту задачу за разумное время помогает
Общая идея динамического программирования заключается в том, что мы рассматриваем вместо одной задачи целое семейство задач. Это семейство задач у нас будет таким: найти наилучший путь из вершины <math>(i, j)</math>. Для каждой пары <math>i, j</math> получим одну задачу. При <math>i = 1</math> и <math>j = 1</math> получается исходная задача, которую нам нужно решить.
По сути, идея динамического программирования заключается в запоминании вычисленных значений <math>(i, j)</math>. Их можно рассматривать как двумерный массив, элементы которого пошагово вычисляются с последней строчки, снизу — вверх.
Подсчитаем количество шагов алгоритма, основанного на динамике. Если количество строк <math>N</math>, то длины строк представляют собой последовательные натуральные числа <math>1, 2,
=== Задача 5 ===
Пусть значения чисел <math>a(i, j)</math> в треугольнике не хранятся в массиве, а быстро вычисляются некоторой внешней функцией от двух аргументов. Придумайте алгоритм, который использует память <math>\Theta(N)</math> и работает время <math>\Theta(N^2)</math>.
Эта задача показывает, что придумать рекурсивный алгоритм часто намного проще, чем не рекурсивный. Также несложно добавить к рекурсии запоминание вычисленных значений. Но нередко существует более быстрый алгоритм, основанный на динамическом программировании, который использует меньше памяти, нежели рекурсия с запоминанием, и делает в два раза
== Задача «Сделай палиндром» ==
Палиндром — это последовательность символов, которая слева-направо и справа-налево пишется одинаково. Например
Длина последовательности не больше 20 символов. Ограничение на время работы программы: 5 секунд.
Эта задача давалась на районной олимпиаде школьников Удмуртской республики в 1998
Если строка имеет вид <math>{h\; \alpha\; t}</math>, где <math>h</math> и <math>t</math> символы, а <math>\alpha</math>
Базой рекурсии являются строки из одного символа и пустая строка — все они полиндромы по определению, и для них <math>S
<math>S(h\; \alpha\; t) = \begin{cases} S(\alpha), & h = t;\\ \min \Big( S(\alpha\, t) + 1,\; S(h\, \alpha) + 1,\; S(\alpha) + 2 \Big), & h \ne t. \end{cases}</math>
Получается, что функция <math>S</math> иногда три раза вызывает себя для меньших строк, чтобы затем из результатов выбрать минимальный. Легко заметить, что тут много повторных вычислений. Избавиться от них поможет запоминание значений <math>S</math> при различных <math>x</math>, которые встречались при вычислении. Однако, тут есть одна техническая проблема. Заметим, что <math>x</math> — это строка. Получается, нужно быстро запоминать и находить значения по заданной строке. Эту задачу решают хэш-таблицы. Но в данном случае можно обойтись и без них. Ясно, что в качестве <math>x</math> могут выступать лишь подстроки исходной строки, то есть некоторые кусочки подряд идущих символов из исходной строки. Каждая подстрока определяется двумя числами — номером первого символа и номером последнего.
Соответственно, получается двупараметрическое семейство задач. Задача <math>P(i, j)</math>, где <math>j > i</math>, есть поиск решения для строки, составленной из символов исходной строки с <math>i</math>-го по <math>j</math>-й символ включительно. Ответы на эти задачи естественно хранить в обычном двумерном массиве. Задачи <math>P(i, i)</math> и <math>P(i, i + 1)</math> имеют очевидное решение <math>S = 0</math>. То есть «диагональ массива» и следующая сверху «диагональ» заполнены нулями. На следующем шаге можно решить задачи вида <math>P(i, i + 2)</math>, затем <math>P(i, i + 3)</math> и так далее. В конце концов мы доберёмся до задачи <math>P(1, n)</math>, соответствующей исходной задаче (<math>n</math> — длина данного слова).
== Алгоритм Евклида ==
Даны два натуральных числа. Найти самое большое натуральное число, которое делит оба без остатка. Такое число называется [[w:Наибольший общий делитель|наибольший общий делитель]] (НОД) (GCD — Greatest Common Divisor).
''Пример:'' Вход: <code>18, 600</code> Выход: <code>6</code>
Есть очень простой алгоритм: давайте перебирать все числа от минимального из заданных до 1 и проверять, делит ли очередное число оба заданных. Первое такое число и будет НОД. У этого алгоритма есть существенный недостаток — маленькая скорость работы. Например для чисел <math>1\,000\,000\,001</math> и <math>1\,000\,000\,000</math> придётся выполнить <math>1\,000\,000\,000</math> проверок. Более эффективно эту задачу решает [[w:Алгоритм Евклида|алгоритм Евклида]], основанный на двух простых свойствах <math>\operatorname{GCD}(a, b)</math>:
# <math>GCD(a, Ka) = a</math>, где <math>K</math> — натуральное число;
# Если <math>a < b</math>, то <math>GCD(a, b) = GCD(a, b - a)</math>.
Рассмотрим второе свойство. При замене одного из чисел на его разность с первым, наибольший общий делитель остаётся прежним.
Если после вычитания <math>b - a</math> получается число, большее <math>a</math>, операцию вычитания можно повторить. Так можно продолжать, пока разность не станет меньше <math>a</math>. Можно догадаться, что вместо нескольких вычитаний достаточно выполнить одну операцию деления с остатком и взять получившийся остаток. Запишем формулы, которые позволят нам определить рекурсивную функцию вычисления НОД:
<math>GCD(a, b)= \begin{cases}
a, & b = Ka, \\
b, & a = Kb, \\
GCD(a,\; b\ \operatorname{mod}\ a), & b \geqslant a; \\
GCD(a\ \operatorname{mod}\ b,\; b), & a \geqslant b.
\end{cases}</math>
Запись «<math>a\ \operatorname{mod}\ b</math>» означает «остаток при делении <math>a</math> на <math>b</math>». Здесь <math>K</math> — натуральное число.
Оценить количество шагов данного алгоритма достаточно сложно, но скорость его очень велика. Хватит 50 шагов этого алгоритма, чтобы найти НОД любой пары чисел, каждое из которых не превышает <math>2\,000\,000\,000</math>. Интересно отметить, что дольше всего алгоритм работает тогда, когда данные числа есть пара соседних чисел Фибоначчи. Число шагов в алгоритме Евклида напрямую связано с длиной разложения рационального числа <math>\frac{a}{b}</math> в ''цепную дробь''. Разложением положительного числа <math>x</math> в цепную дробь называется представление <math>x = a_0 + a_1 / (a_2 + 1 /(a_3 + 1/(a_4 + \dots)))</math>, где числа <math>a_i</math> натуральные. Разложение дробей (рациональных чисел) в цепную дробь конечно. Вот примеры разложений отношений соседних чисел Фибоначчи в цепную дробь:
<math>\frac{3}{5} = \frac{1}{\displaystyle 1 + \frac{1}{\displaystyle 1 + \frac{1}{2}}}</math>, <math>\frac{5}{8}=\frac{1}{\displaystyle 1 + {\displaystyle \frac{1}{\displaystyle 1 + {\frac{1}{\displaystyle 1 + \frac{1}{2}}}}}}</math>, <math>\frac{8}{13}=\frac{1}{\displaystyle 1+{\displaystyle \frac{1}{\displaystyle 1 + {\frac{1}{\displaystyle 1 + \frac{1}{ \displaystyle 1 + \frac{1}{2}}}}}}}</math>.
=== Задача 6 ===
Докажите, что разложение в цепную дробь эквивалентно алгоритму Евклида. Докажите, что <math>\operatorname{GCD}(F(n + 1),\; F(n)) = 1</math> и число шагов в алгоритме Евклида для пары <math>\Big( F(n+1),\; F(n) \Big)</math> равно <math>n</math>. Верно ли, что <math>F(50) > 2\,000\,000\,000</math>?
=== Задача 7 ===
Докажите, что на парах вида <math>\Big( k,\; F(n+1) \Big)</math>, <math>k=1, 2, \dots, F(n + 1) - 1</math> алгоритм Евклида дольше всего работает при <math>k = F(n)</math>, и число шагов алгоритма при этом равно <math>n</math>.
При построении рекурсивной функции важно ответить на следующие вопросы:
# Что будет базой рекурсии?
# Что будет шагом рекурсии?
# Почему выполнение шагов рекурсии всегда приведёт к базе?
# Какова будет глубина рекурсии при данном значении аргументов? Глубина
# Как растёт размер дерева рекурсивных вызовов при увеличении входных данных?
Одно из важных достоинств рекурсивных алгоритмов заключается в том, что они просты и наглядны. Но рекурсия не всегда является эффективным (самым быстрым) решением. Рекурсия использует мало памяти, но работать может довольно долго, как в примере с числами Фибоначчи.
=== Задача 8 ===
Есть несколько алгоритмов Евклида, основанных на различных рекуррентных соотношениях для НОД:
# <math>\operatorname{GCD}(a, b) = \operatorname{GCD}(b, a\ \operatorname{mod}\ b)</math>;
# <math>\operatorname{GCD}(a, b) = \operatorname{GCD}(b, \min(|a\ \operatorname{mod}\ b|,\; b - |a\ \operatorname{mod}\ b|);</math>
# <math>\operatorname{GCD}(a, b) = \begin{cases}
\operatorname{GCD} \left( a,\; \frac{b}{2^k} \right), & a \mbox{ is odd, and } b = b' \cdot 2^k, \\
2^k \cdot \operatorname{GCD} \left( \frac{a}{2^k},\; \frac{b}{2^k} \right), & a \mbox{ and } b \mbox{ are even, and } a = a' \cdot 2^k,\; b = b' \cdot 2^k, \\
\operatorname{GCD}(b,\; a - b), & a \mbox{ and } b \mbox{ are odd, and } a > b.
\end{cases}</math>
Эффективность этих алгоритмов можно оценивать с помощью среднего числа шагов алгоритма, необходимых для вычисления <math>\operatorname{GCD}(m, N)</math>, где <math>N</math> фиксированно, а <math>m</math> пробегает значения <math>1, 2, \dots, N - 1</math>. Известно, что это число примерно пропорционально <math>\log_2 N</math>. Вычислите экспериментально коэффициенты пропорциональности для указанных трёх случаев. Явные выражения для этих коэффициентов довольно сложны.
== Задачи для самостоятельного решения ==
Существуют и другие задачи, решаемые рекурсией и динамическим программированием. Вот самые известные: обход конём шахматной доски, задача о восьми ферзях, триангуляция, поиск пути в лабиринте, вычисление арифметического выражения и многое другое.
Строка 215 ⟶ 219 :
Ниже предлагается несколько простых задач, для знакомства с идеей рекурсии.
=== Задача 9 ===
Напишите две
# <math>
# <math>a^n = \begin{cases}
a^{\frac{n}{2}} \cdot a^{\frac{n}{2}}, & \mbox{ if } n \mbox{ is even,}\\
a \cdot a^{n - 1}. & \mbox{ if } n \mbox{ is odd,}
\end{cases}</math>
База рекурсии в обоих случаях <math>f(a, 0) = a^0 = 1</math>. Какое получается дерево рекурсивных вызовов при <math>n = 1000</math>? Имеет ли смысл запоминать вычисленные значения? Чему равно число шагов при <math>n = 1000</math>? Какая из процедур оказалась более эффективной? Покажите, что в случае (2) число рекурсивных вызовов (число вершин в дереве рекурсивных вызовов) ограничено сверху числом <math>2(\log_2 n + 1)</math>.
=== Задача 10 ===
[[Изображение: graphpaths.jpg]]
Найдите число различных путей из точки <math>A</math> в точку <math>B</math> по стрелочкам. Напишите программу, которая для вычисляет число этих путей для таких треугольных конфигураций (графов) со стороной <math>n</math>.
===Задача 11===
Число правильных скобочных структур длины 6 равно 5: <code>()()()</code>, <code>(())()</code>, <code>()(())</code>, <code>((()))</code>, <code>(()())</code>.
Напишите рекурсивную программу генерации всех правильных скобочных структур длины <math>2n</math>. Определение правильной скобочной структуры можно задать в нотации EBNF (в расширенной [[w:Форма Бэкуса — Наура|форме Бэкуса — Наура]]) рекурсивно:
<source lang="bnf">s ::= '(' s ')' | s s | ''</source>
Эта строчка содержит рекурсивное определение объекта <code>s</code>: «объект типа <code>s</code> может быть получен из объекта типа <code>s</code> с помощью окружения его открывающейся и закрывающейся круглой скобки, или с помощью приписывания двух объектов типа <code>s</code> друг к другу, либо это просто пустое слово». Вертикальная черта в нотации EBNF означает союз «или». С помощью одинарных кавычек выделяют символы или строки символов, пробелы играют роль разделителей.
=== Задача 12 ===
Чему равно число <math>c_n</math> правильных скобочных структур длины <math>2n</math>? Найдите рекуррентную формулу для числа <math>c_n</math>, а именно выразите <math>c_n</math> через все предыдущие <math>c_{n-1}, \dots, <math>c_1</math>. Напишите программу, которая вычисляет число <math>c_n</math> правильных скобочных структур длины <math>2n</math>.
''Подсказка:'' найдите перебором первые элементы последовательности <math>c_n = \{1, 2, 5, \dots \}</math>. Рассмотрите соотношения соседних элементов и догадайтесь до явной формулы.
''Второй способ.'' Задача решается методом динамического программирования. Число различных путей из <math>A</math> в <math>B</math> по стрелкам на рисунке из задачи 10 равно числу правильных скобочных структур длины 6 (стрелка вверх соответствует открывающей скобке, а стрелка вниз — закрывающей). Придумайте способ последовательного вычисления числа различных путей из вершины <math>A</math> до различных вершин графа. Сколько памяти использует ваша программа для вычисления <math>c_n</math> в зависимости от <math>n</math>?
=== Задача 13 ===
Известный алгоритм [[w:Быстрая сортировка|быстрой сортировки Хоара]] также основан на рекурсии. Пусть нам нужно отсортировать кусочек массива <math>A</math> от элемента с индексом <math>b</math> по элемент с индексом <math>e</math> включительно. Перераспределим элементы на этом кусочке так, чтобы вначале стояли элементы меньшие либо равные <math>A_b</math>, а потом элементы большие либо равные <math>A_b</math>. Пусть последний элемент в первом кусочке оказался на месте <maht>c</math>. Вызовем рекурсивно сортировку двух кусочков от <math>b</math> до <math>c</math> и от <math>c + 1</math> до <math>e</math> включительно, (если, конечно, эти кусочки состоят более, чем из одного элемента). Воплотите эту идею в работающую процедуру сортировки массива. Проведите эксперименты по оценке средней глубины дерева рекурсии и времени работы алгоритма в зависимости от размера массива. Рассмотрите случаи а) случайного массива, б) массива, упорядоченого по возрастанию, и в) массива, упорядоченного по убыванию.
== Задача коммивояжёра ==
Рекурсия с запоминанием работает не всегда. Рассмотрим пример задачи, для которой есть долго работающий рекурсивный алгоритм, который нельзя существенно ускорить с помощью запоминания вычисленных значений.
Наш коммивояжёр ездит по городам с целью сбыта товаров разного рода. Он всегда начинает и заканчивает свой путь в одном и том же городе. На проживание во всех городах коммерсант тратит одинаковую сумму денег. Поэтому существенна только сумма на проезд из города в город. Есть список городов и стоимость проезда между некоторыми парами городов.
Задача коммивояжёра — побывать во всех городах (ровно по одному разу) и при этом потратить как можно меньше денег на проезд и вернуться обратно.
'''Формулировка задачи'''
* внутри города проезд ничего не стоит;
* проезд между двумя городами напрямую стоит одинаково в оба конца;
* стоимость — целое число от 1 до 10000;
* городов не более 100.
Стоимости проезда между парами городов записаны в следующем формате:
<Количество стоимостей> <Начальный город>
<Город> <Город> <Стоимость>
<Город> <Город> <Стоимость>
<Город> <Город> <Стоимость>
Результат записывается в следующем формате:
<Количество городов в пути>
<Город>
Город задаётся названием без пробела. Длина названия города не более 30 символов. Программа должна реагировать на клавишу ESC. Если ESC была нажата, то в течении 10 секунд программа должна записать результат и закончить работу.
Кажется, что для решения такой задачи достаточно хранить самые оптимальные промежуточные пути и вот он динамический алгоритм. Например, рассмотрим тройки городов и для каждой тройки определим в какой последовательности лучше всего её проходить. Затем рассмотрим все четвёрки городов. Решения для четвёрок можно найти на основе известных решений для троек и так далее. Но дело в том, что число возможных наборов <math>k</math> городов и <math>n</math> возможных очень быстро растёт с <math>n</math> и <math>k</math>. Например, 50 городов из 100 можно выбрать 100 891 344 545 564 193 334 812 497 256 способами. Таким образом, запоминать промежуточные решения нет никакой возможности — их слишком много даже для <math>n = 100</math>, а на практике нужно решать задачи с <math>n = 10^6</math>. Для задачи коммивояжёра на плоскости можно использовать ряд эвристических идей, которые позволяют находить приемлемые решения за разумное время. Но при этом даже для случая точек на плоскости задача коммивояжёра остаётся полиномиально неразрешимой, то есть не существует алгоритма, который бы находил самый оптимальный путь коммивояжёра за время ограниченное полиномом <math>C + n^k</math> произвольной степени <math>k</math> при любой константе <math>C</math>.
== Снежинка Коха ==
[[w:Снежинка Коха|Снежинка Коха]] — это фрактальное множество точек на плоскости, которое похоже на снежинку.
Строка 302 ⟶ 301 :
Здесь приведена программа на языке [[w:PostScript|PostScript]]. Этот код интерпрерируется программой GSView, которую можно взять на сайте http://www.ghostscript.com.
Снежинка рисуется рекурсивным образом.
В математике, в отличие от программирования, допускаются такие бесконечные рекурсивные определения. На каждом шаге у нас получается некоторая обычная фигура (не фрактал), а в пределе (после бесконечного числа шагов) получается фрактал.
'''Задача.'''
Программа «Снежинка Коха»
<code>%!PS-Adobe
/inch {72 mul} def
Строка 354:
showpage</code>
== Заключение ==
Рекурсивный метод решения задач является чуть ли не базовым методом решения алгоритмических задач. Рекурсия, дополненная идеями динамического программирования, жадными алгоритмами и идеей отсечения, превращается в тяжёлую артиллерию программистов. Но не следует забывать, что краткость записи рекурсивных функций не всегда означает высокую скорость их вычисления. И есть ряд задач, в которых рекурсия просто вредна (такова, например, задача вычисления кратчайшего пути в графе).
== Дальнейшее чтение ==
<references/>
[[Категория:Информатика]] [[Категория:Журнал «Потенциал»]][[Категория:информатика в журнале «Потенциал»]]
|