Глава 8 как обойтись без рекурсии


Содержание

Когда рекурсия не нужна

При новом рекурсивном вызове компьютер делает так:

1. Запоминается состояние вычислений на данном этапе.

2. В стеке (особой области памяти) создается новыйнабор локальных переменных (чтобы

не испортить переменные текущего вызова).

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

глубина рекурсии(количество вложенных вызовов) должна была достаточно мала.

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

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

Например, задача вычисления факториала очень просто решается с помощью обычного цикла

for(такое решение с помощью циклов называют итеративным, циклическим):

Int Factorial ( int n )

int i, fact = 1;

for ( i = 2; i 1.

Использование рекурсии «в лоб» дает функцию

Int Fib ( int n )

if ( n == 0 ) return 0;

if ( n == 1 ) return 1;

return Fib(n-1) + Fib(n-2);

Заметим, что каждый рекурсивный вызов при n > 1порождает еще 2 вызова функции, многие выражения (числа Фибоначчи для малых n) вычисляются много раз. Поэтому практического значения этот алгоритм не имеет, особенно для большихn. Схема вычисления Fib(5)показана в виде дерева ниже:

Заметим, что очередное число Фибоначчи зависит только от двух предыдущих, которые будем хранить в переменных f1и f2. Сначала примем f1=1и f2=0, затем вычисляем следующее число Фибоначчи и записываем его в переменную x. Теперь значение f2уже не нужно и мы скопируем f1в f2и xв f1.

Int Fib2(int n)

int i, f1 = 1, f2 = 0, x;

for (i = 2; i 20) работает в сотни тысяч (. ) раз быстрее, чем рекурсивная. Вывод: там, где можно легко обойтись без рекурсии, надо без нее обходиться.

Рекурсивный поиск

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

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

1) ищем первое заданное слово с помощью функции strstr; если не нашли, то стоп;

2) количество слов = 1 + количество слов в оставшейся части строки.

int HowMany( char *s, char *word )

char *p = strstr(s, word); // ищемпервоеслово

if ( ! p ) return 0; // ненашли – 0 слов

return 1 + // одноуженашли, .

HowMany(p+strlen(word),word); // ищемдальше

Функция получилась короткая, понятная, но по скорости работы не самая эффективная.

Рекурсивные фигуры

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

стей еще меньшего диаметра и т.д. Всего – Nразных диаметров (Nуровнейрекурсии).

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Как то на паре, один преподаватель сказал, когда лекция заканчивалась — это был конец пары: «Что-то тут концом пахнет». 8378 — | 8008 — или читать все.

188.64.174.135 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

«Рекурсивная функция» (Обход бинарного дерева)

первый параметр это указатель на элемент дерева, а второй — уровень на катором находиться узел.
Объясните пожалуйста принцип работы такой функции. Заранее благодарен )

Добавлено через 1 минуту
вот сама структура:

08.03.2010, 10:40

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

Разница между понятиями «Обход в прямом направлении» и «Итерационный прямой обход»
Ребятаа, обьясните чем различается: Обход в прямом направлении и Итерационный прямой обход .

Рекурсивная функция берет значение из «ниоткуда»
Обычное построение дерева отрезков. #include #include #include .

Обход бинарного дерева
может есть у кого такой пример или похожий??или часть какая нибудь?

Обход Бинарного дерева
Задача: написать функцию, помощью которой можно получить n-тый элемент бинарного дерева по.

08.03.2010, 10:41 2 09.03.2010, 12:46 [ТС] 3

Рекурсивная функция, это функция которая вызыват саму себя

Добавлено через 3 часа 47 минут
Люди, добрые, помjгите разобраться

Добавлено через 22 часа 10 минут
Вот весь код

вот результат программы
1
6
8
10
20
25 21
30

Вот как я понимаю как работает функция print_tree:
вызовы:
1) print_tree(10, 0); (лев. часть)
2) print_tree(6, 1); (лев. часть)
3)print_tree (1, 2); (лев. часть)
4)print_tree(нет левого поддерева, 3) (лев. часть)
вывод «1»
5) print_tree (нет правого поддерева, 3); (лев. часть)

все дальше не понятно как выводиться остальная часть поддерева

Добавлено через 5 минут
небольшая поправка:
5) print_tree (нет правого поддерева, 3); (прав. часть)

09.03.2010, 13:01 4
09.03.2010, 13:01
09.03.2010, 13:05 5
09.03.2010, 13:12 6
09.03.2010, 13:19 [ТС] 7
09.03.2010, 13:31 8
09.03.2010, 13:34 [ТС] 9
09.03.2010, 13:43 10
09.03.2010, 14:02 [ТС] 11
09.03.2010, 14:14 12
09.03.2010, 18:20 13
10.03.2010, 00:57 [ТС] 14
10.03.2010, 08:21 15
10.03.2010, 09:37 16
10.03.2010, 10:03 17
10.03.2010, 11:16 18
10.03.2010, 11:25 19

Извините, но не могу согласиться.

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

Во-вторых, что нам мешает сделать стек поглубже, а стековых переменных — поменьше? Пару гигов на стек — и золотой ключик у нас в кармане. А когда вычисления подходят к границе ресурсов, тут уж поневоле приходится усложнять алгоритмы. Это не только с рекурсией, простая сортировка ведет себя не лучше при возрастании объемов сортируемой информации.

Как решить эту проблему без рекурсии?

Я пытаюсь помочь моему сыну решить математическую проблему. Это кажется хорошей возможностью разоблачить его для некоторых программ. Я вижу рекурсивное решение, но, возможно, итеративный вариант будет легче объяснить. Язык, который он изучил до сих пор, был SmallBasic, который не поддерживает рекурсию очень хорошо (без локальных переменных). Я не против преподавания другого языка, но все же хочу понять, есть ли хороший способ решить эту проблему без рекурсии.

Проблема заключается в следующем: Учитывая последовательность чисел 1 2 3 4 5 6 7 8 9, вставьте + и — между числами, чтобы результат суммировал до 101. Например, 1 + 23 + 4 + 5 + 67-8 + 9 = 101.

Рекурсивное решение выглядит примерно так:

Есть ли итеративное решение для этого, что не слишком сложно?

6 ответов

17 Решение Thomas Kammeyer [2009-03-26 19:51:00]

Рассмотрим пробелы между числами 1 2 3 4 5 6 7 8 9. Есть 8 таких интерстициальных пространств или слотов.

Каждое такое пространство может быть заполнено символом +, — или ничего (с указанием более длинное число).

Это три возможности в каждом из восьми слотов. Назначьте цифры трем возможным наполнителям следующим образом:

Теперь каждая 8-значная триниальная строка соответствует решению. Примеры:

Теперь напишите простой цикл, который считается от 00000000 до 22222222 в trinary. Интерпретируйте каждый номер по пути в качестве решения, как указано выше, остановитесь, как только вы нажмете на решение, уступив цель, 101 или сбой отчета, если вы дойдете до конца, не достигнув целевого значения.

Существует 3 ^ 8 (показатель экспоненты, а не xor или 3 ** 8 для фортаноидов, или

для интенсивно буквально мыслящих) возможных решений. Это всего лишь 6561; вы можете грубо заставить ее таким образом довольно удобно.

Рекурсия — важный момент в информатике. Если ваша цель — научить вашего сына, почему бы вам не объяснить его рекурсию прямо сейчас?;)

2 Seb [2009-03-26 19:50:00]

У вас есть 3 основных операции:

  • Добавить (опция «0» );
  • Substract (опция «1» );
  • Ничего не делать (опция «2» );

Итак, у вас есть 3 ^ 8 возможных решений; просто попробуйте их всех.

Это код PHP, но включает в себя преобразование чисел в другие базы, что-то, что 8-летний мальчик, вероятно, не понял бы быстро. Возможно, вы можете найти поворот для этого:

1 vartec [2009-03-26 19:29:00]

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

0 Richard [2009-03-26 19:29:00]

Учитывая ограниченную глубину рекурсии, массив может использоваться как стек.

Это можно сделать итеративно, но не так просто, как это. Что еще более важно, собираетесь ли вы использовать это как возможность научить вашего сына сложности алгоритма?

Глава 8 как обойтись без рекурсии

. рекурсии.
Для каждой вершины рассмотрим ее «глубину» — максимальную
длину пути по стрелкам, из нее выходящего. Условие отсутствия
циклов гарантирует, что эта величина конечна. Из вершины
нулевой глубины стрелок не выходит. Глубина конца стрелки по
крайней мере на 1 меньше, чем глубина начала. При работе процедуры
add(i) все рекурсивные вызовы add(j) относятся к вершинам
меньшей глубины.

Связная компонента графа. Неориентированный граф — набор
точек (вершин), некоторые из которых соединены линиями (ребрами).
Неориентированный граф можно считать частным случаем ориентированного
графа, в котором для каждой стрелки есть обратная.
Связной компонентой вершины i называется множество всех тех
вершин, в которые можно попасть из i, идя по ребрам графа. (Поскольку
граф неориентированный, отношение «j принадлежит связной
компоненте i» является отношением эквивалентности.)

7.4.5. Дан неориентированный граф (для каждой вершины указано
число соседей и массив номеров соседей, как в предыдущей
задаче). Составить алгоритм, который по заданному i печатает все
вершины связной компоненты i по одному разу (и только их). Число
действий не должно превосходить C*(общее число вершин и ребер в
связной компоненте).

Решение. Программа в процессе работы будет «закрашивать»
некоторые вершины графа. Незакрашенной частью графа будем называть
то, что останется, если выбросить все закрашенные вершины и
ведущие в них ребра. Процедура add(i) закрашивает связную компоненту
i в незакрашенном графе (и не делает ничего, если вершина
i уже закрашена).

procedure add (i:1..n);
begin
| if вершина i закрашена then begin
| | ничего делать не надо
| end else begin
| | закрасить i (напечатать и пометить как закрашенную)
| | для всех j, соседних с i
| | | add(j);
| | end;
| end;
end;

Докажем, что эта процедура действует правильно (в предположении,
что рекурсивные вызовы работают правильно). В самом деле, ничего,
кроме связной компоненты незакрашенного графа, она закрасить
не может. Проверим, что вся она будет закрашена. Пусть k — вершина,
доступная из вершины i по пути i-j-. -k, проходящему
только по незакрашенным вершинам. Будем рассматривать только пути,
не возвращающиеся снова в i. Из всех таких путей выберем
путь с наименьшим j (в порядке просмотра соседей в цикле в процедуре).
Тогда при рассмотрении предыдущих соседей ни одна из
вершин j-. -k не будет закрашена (иначе j не было бы минимальным)
и потому k окажется в связной компоненте незакрашенного
графа к моменту вызова add(j). Что и требовалось.
Чтобы установить конечность глубины рекурсии, заметим, что
на каждом уровне рекурсии число незакрашенных вершин уменьшается
хотя бы на 1.
Оценим число действий. Каждая вершина закрашивается не более
одного раза — при первым вызове add(i) с данным i. Все последующие
вызовы происходят при закрашивании соседей — количество
таких вызовов не больше числа соседей — и сводятся к проверке
того, что вершина i уже закрашена. Первый же вызов состоит в
просмотре всех соседей и рекурсивных вызовах add(j) для всех
них. Таким образом, общее число действий, связанных с вершиной
i, не превосходит константы, умноженной на число ее соседей. Отсюда
и вытекает требуемая оценка.

7.4.6. Решить ту же задачу для ориентированного графа (напечатать
все вершины, доступные из данной по стрелкам; граф может
содержать циклы).

Ответ. Годится по существу та же программа (строку «для
всех соседей» надо заменить на «для всех вершин, куда ведут
стрелки»).

Быстрая сортировка Хоара. В заключение приведем рекурсивный
алгоритм сортировки массива, который на практике является одним
из самых быстрых. Пусть дан массив a[1]..a[n]. Рекурсивная процедура
sort (l,r:integer) сортирует участок массива с индексами
из полуинтервала (l,r] (т.е. a[l+1]..a[r]), не затрагивая остального
массива.

procedure sort (l,r: integer);
begin
| if (l = r) then begin
| | ничего делать не надо — участок пуст
| end else begin
| | выбрать случайное число s в полуинтервале (l,r]
| | b := a[s]
| | переставить элементы сортируемого участка так, чтобы
| | сначала шли элементы, меньшие b — участок (l,ll]
| | затем элементы, равные b — участок (ll,rr]
| | затем элементы, большие b — участок (rr,r]
| | sort (l,ll);
| | sort (rr,r);
| end;
end;

Перестановка элементов сортируемого участка рассматривалась в
главе о массивах (это можно сделать за время, пропорциональное
длине участка). Конечность глубины рекурсии гарантируется тем,
что длина сортируемого участка на каждом уровне рекурсии
уменьшается хотя бы на 1.

7.4.7. (Для знакомых с основами теории вероятностей). Доказать,
что математическое ожидание числа операций при работе этого
алгоритма не превосходит C*n*log n, причем константа C не зависит
от сортируемого массива.

Указание. Пусть T(n) — максимум математического ожидания
числа операций для всех входов длины n. Из текста процедуры вытекает
такое неравенство:

T(n) «= Cn + 1/n [сумма по всем k+l=(n-1) чисел T(k)+T(l)]

Первый член соответствует распределению элементов на меньшие,
равные и большие. Второй член — это среднее математическое ожидание
для всех вариантов случайного выбора. (Строго говоря, поскольку
среди элементов могут быть равные, в правой части вместо
T(k) и T(l) должны стоять максимумы T(x) по всем x, не превосходящим
k или l, но это не мешает дальнейшим рассуждениям.) Далее
индукцией по n нужно доказывать оценку T(n) «= C’nlog n. При
этом для вычисления среднего значения x log x по всем
x=1. n-1 нужно интегрировать x lnx по частям как lnx * d(x*x).
При достаточно большом C’ член Cn в правой части перевешивается
за счет интеграла x*x*d(ln x), и индуктивный шаг проходит.

7.4.8. Имеется массив из n различных целых чисел a[1]..a[n]
и число k. Требуется найти k-ое по величине число в этом массиве,
сделав не более C*n действий, где C — некоторая константа,
не зависящая от k.

Замечание. Сортировка позволяет очевидным образом сделать
это за C*n*log(n) действий. Очевидный способ: найти наименьший
элемент, затем найти второй, затем третий. k-ый требует порядка
k*n действий, то есть не годится (константа при n зависит
от k).

Указание. Изящный (хотя практически и бесполезный —
константы слишком велики) способ сделать это таков:
А. Разобьем наш массив на n/5 групп, в каждой из которых по
5 элементов. Каждую группу упорядочим.
Б. Рассмотрим средние элементы всех групп и перепишем их в
массив из n/5 элементов. С помощью рекурсивного вызова найдем
средний по величине элемент этого массива.
В. Сравним этот элемент со всеми элементами исходного массива:
они разделятся на большие его и меньшие его (и один равный
ему). Подсчитав количество тех и других, мы узнаем, в какой из
этих частей должен находится искомый (k-ый) элемент и каков он
там по порядку.

Г. Применим рекурсивно наш алгоритм к выбранной части.

Пусть T(n) — максимально возможное число действий, если
этот способ применять к массивам из не более чем n элементов (k
может быть каким угодно). Имеем оценку:
T(n) «= Cn + T(n/5) + T(примерно 0.7n)
Последнее слагаемое объясняется так: при разбиении на части каждая
часть содержит не менее 0.3n элементов. В самом деле, если x
— средний из средних, то примерно половина всех средних меньше
x. А если в пятерке средний элемент меньше x, то еще два заведомо
меньше x. Тем самым по крайней мере 3/5 от половины элементов
меньше x.
Теперь по индукции можно доказать оценку T(n) «= Cn (решающую
роль при этом играет то обстоятельство, что 1/5 + 0.7 » 1).

Глава 8. Как обойтись без рекурсии.

Для универсальных языков программирования (каковым является
паскаль) рекурсия не дает ничего нового: для всякой рекурсивной
программы можно написать эквивалентную программу без рекурсии.
Мы не будем доказывать этого, а продемонстрируем некоторые приемы,
позволяющие избавиться от рекурсии в конкретных ситуациях.
Зачем это нужно? Ответ прагматика мог бы быть таким: во
многих компьютерах (в том числе, к сожалению, и в современных,
использующих так называемые RISC-процессоры), рекурсивные программы
в несколько раз медленнее соответствующих нерекурсивных
программ. Еще один возможный ответ: в некоторых языках программирования
рекурсивные программы запрещены. А главное, при удалении
рекурсии возникают изящные и поучительные конструкции.

8.1. Таблица значений (динамическое программирование)

8.1.1. Следующая рекурсивная процедура вычисляет числа сочетаний
(биномиальные коэффициенты). Написать эквивалентную нерекурсивную
программу.

function C(n,k: integer):integer;
|
begin
| if (k = 0) or (k = n) then begin
| | C:=1;
| end else begin <0"k"n>
| | C:= C(n-1,k-1)+C(n-1,k)
| end;
end;

Замечание. C(n,k) — число k-элементных подмножеств n-элементного
множества. Соотношение C(n,k) = C(n-1,k-1)+C(n-1,k) получится,
если мы фиксируем некоторый элемент n-элементного множества и
отдельно подсчитаем k-элементные множества, включающие и не
включающие этот элемент. Таблица значений C(n,k)

1 1
1 2 1
1 3 3 1
называется треугольником Паскаля (того самого). В нем каждый
элемент, кроме крайних единиц, равен сумме двух стоящих над ним.

Решение. Можно воспользоваться формулой
C(n,k) = n! / (k! * (n-k)!)
Мы, однако, не будем этого делать, так как хотим продемонстрировать
более общие приемы устранения рекурсии. Составим таблицу
значений функции C(n,k), заполняя ее для n = 0, 1, 2. пока
не дойдем до интересующего нас элемента.

8.1.2. Что можно сказать о времени работы рекурсивной и нерекурсивной
версий в предыдущей задаче? Тот же вопрос о памяти.

Решение. Таблица занимает место порядка n*n, его можно сократить
до n, если заметить, что для вычисления следующей строки
треугольника Паскаля нужна только предыдущая. Время работы в
обоих случаях порядка n*n. Рекурсивная программа требует существенно
большего времени: вызов C(n,k) сводится к двум вызовам
для C(n-1. ), те — к четырем вызовам для C(n-2. ) и т.д. Таким
образом, время оказывается экспоненциальным (порядка 2 в степени
n). Используемая рекурсивной версией память пропорциональна n —
умножаем глубину рекурсии (n) на количество памяти, используемое
одним экземпляром процедуры (константа).

Кардинальный выигрыш во времени при переходе от рекурсивной версии
к нерекурсивной связан с тем, что в рекурсивном варианте одни
и те же вычисления происходят много раз. Например, вызов
C(5,3) в конечном счете порождает два вызова C(3,2):

C(5,3)
/ \
C(4,2) C(4,3)
/ \ / \
C(3,1) C(3,2) C(3,3)
Заполняя таблицу, мы каждую клетку заполняем только однажды —
отсюда и экономия. Этот прием называется динамическим программированием,
и применим в тех случаях, когда объем хранимой в таблице
информации оказывается не слишком большим.

8.1.2. Порассуждать на ту же тему на примере рекурсивной и
(простейшей) нерекурсивной программ для вычисления чисел Фибоначчи,
заданных соотношением
f(1) = f (2) = 1; f(n) = f(n-1) + f(n-2) для n » 2.


8.1.3. Дан выпуклый n-угольник (заданный координатами своих
вершин в порядке обхода). Его разрезают на треугольники диагоналями,
для чего необходимо n-2 диагонали (докажите индукцией по
n). Стоимостью разрезания назовем сумму длин всех использованных
диагоналей. Найти минимальную стоимость разрезания. Число
действий должно быть ограничено некоторым многочленом от n. (Перебор
не подходит, так как число вариантов не ограничено многочленом.)

Решение. Будем считать, что вершины пронумерованы от 1 до n
и идут по часовой стрелке. Пусть k, l — номера вершин, причем
l»k. Через A(k,l) обозначим многоугольник, отрезаемый от нашего
хордой k—l. (Эта хорда разрезает многоугольник на 2, один из
которых включает сторону 1—n; через A(k,l) мы обозначаем другой.)
Исходный многоугольник естественно обозначить A(1,n). При
l=k+1 получается «двуугольник» с совпадающими сторонами.

Через a(k,l) обозначим стоимость разрезания многоугольника
A(k,l) диагоналями на треугольники. Напишем рекуррентную формулу
для a(k,l). При l=k+1 получается двуугольник, и мы полагаем
a(k,l)=0. При l=k+2 получается треугольник, и в этом случае также
a(k,l)=0. Пусть l » k+2. Хорда k—l является стороной многоугольника
A(k,l) и, следовательно, стороной одного из треугольников,
на которые он разрезан. Противоположной вершиной i
этого треугольника может быть любая из вершин k+1. l-1, и минимальная
стоимость разрезания может быть вычислена как

по всем i=k+1. i=l-1. При этом надо учесть, что при i=k+1
хорда k—i — не хорда, а сторона, и ее длину надо считать равной
0 (по стороне разрез не проводится).

Составив таблицу для a(k,l) и заполняя ее в порядке возрастания
числа вершин (равного l-k+2), мы получаем программу, использующую
память порядка n*n и время порядка n*n*n (однократное
применение рекуррентной формулы требует выбора минимума из не
более чем n чисел).

8.1.4. Матрицей размера m*n называется прямоугольная таблица
из m строк и n столбцов, заполненная числами. Матрицу размера
m*n можно умножить на матрицу размера n*k (ширина левого сомножителя
должна равняться высоте правого), и получается матрица
размером m*k. Ценой такого умножения будем считать произведение
m*n*k (таково число умножений, которые нужно выполнить при стандартном
способе умножения — но сейчас это нам не важно). Умножение
матриц ассоциативно, поэтому произведение n матриц можно вычислять
в разном порядке. Для каждого порядка подсчитаем суммарную
цену всех матричных умножений. Найти минимальную цену вычисления
произведения, если известны размеры всех матриц. Число
действий должно быть ограничено многочленом от числа матриц.

Пример. Матрицы размером 2*3, 3*4, 4*5 можно перемножать
двумя способами. В первом цена равна 2*3*4 + 2*4*5 = 24 + 40 =
64, во втором цена равна 3*4*5 + 2*3*5 = 90.

Решение. Представим себе, что первая матрица написана на
отрезке [0,1], вторая — на отрезке [1,2]. s-ая — на отрезке
[s-1,s]. Матрицы на отрезках [i-1,i] и [i,i+1] имеют общий размер,
позволяющих их перемножить. Обозначим его через d[i]. Таким
образом, исходным данным в задаче является массив d[0]..d[s].
Через a(i,j) обозначим минимальную цену вычисления произведения
матриц на участке [i,j] (при 0″=i»j»=s). Искомая величина
равна a(0,s). Величины a(i,i+1) равны нулю (матрица одна и перемножать
ничего не надо). Рекуррентная формула будет такой:

где минимум берется по всем возможных местам последнего умножения,
то есть по всем k=i+1..j-1. В самом деле, произведение матриц
на отрезке [i,k] есть матрица размера d[i]*d[k], произведение
матриц на отрезке [k,j] имеет размер d[k]*d[j], и цена вычисления
их произведения равна d[i]*d[k]*d[j].

Замечание. Две последние задачи похожи. Это сходство станет
яснее, если написать матрицы — множители на сторонах 1—2,
2—3. s-1—s многоугольника, а на каждой хорде i—j написать
произведение всех матриц, стягиваемых этой хордой.

8.1.5. Железная дорога с односторонним движением имеет n
станций. Известны цены белетов от i-ой станции до j-ой (при i «
j — в обратную сторонону проезда нет). Найти минимальную стоимость
проезда от начала до конца (с учетом возможной экономии
за счет пересадок).

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

8.1.6. Задано конечное множество с бинарной операцией (вообще
говоря, не коммутативной и даже не ассоциативной). Имеется
n элементов a[1]..a[n] этого множества и еще один элемент x.
Проверить, можно ли так расставить скобки в произведении
a[1]..a[n], чтобы в результате получился x. Число операций
должно не превосходить C*n*n*n для некоторой константы C (зависищей
от числа элементов в выбранном конечном множестве).

Решение. Заполняем таблицу, в которой для каждого участка
a[i]..a[j] нашего произведения хранится список всех возможных
его значений (при разной расстановке скобок).

По существу этот же прием применяется в полиномиальном алгоритме
проверки принадлежности слова произвольному контекстно-свободному
языку (см. главу 13).

Следующая задача (задача о рюкзаке) уже упоминалась в главе
3 (Обход дерева).

8.1.7. Имеется n положительных целых чисел x[1]..x[n] и
число N. Выяснить, можно ли получить N, складывая некоторые из
чисел x[1]..x[n]. Число действий должно быть порядка N*n.
Указание. После i шагов хранится множество тех чисел на отреке
0..N, которые предствимы в виде суммы некоторых из
x[1]..x[i].

8.2. Стек отложенных заданий.

Другой прием устранения рекурсии продемонстрируем на примере
задачи о ханойских башнях.

8.2.1. Написать нерекурсивную программу для нахождения последовательности
перемещений дисков в задаче о ханойских башнях.

Решение. Вспомним рекурсивную программу:

procedure move(i,m,n: integer);
| var s: integer;
begin
| if i = 1 then begin
| | writeln (‘сделать ход’, m, ‘-«‘, n);
| end else begin
| | s:=6-m-n;
| | move (i-1, m, s);
| | writeln (‘сделать ход’, m, ‘-«‘, n);
| | move (i-1, s, n);
| end;
end;

Знакомства

Видно, что задача «переложить i верхних дисков с m-го стержня на
n-ый» сводится к трем задачам того же типа: двум задачам с i-1
дисками и к одной задаче с единственным диском. Выполняя эти задачи,
важно не позабыть, что еще осталось сделать.

Для этой цели заведем стек отложенных заданий, элементами
которого будут тройки «i,m,n». Каждая такая тройка интерпретируется
как заказ «переложить i верхних дисков с m-го стержня на
n-ый». Заказы упорядочены в соответствии с требуемым порядком их
выполнения: самый срочный — вершина стека. Получам такую программу:

procedure move(i,m,n: integer);
begin
| сделать стек заказов пустым
| положить в стек тройку «i,m,n»
| <инвариант: осталось выполнить заказы в стеке>
| while стек непуст do begin
| | удалить верхний элемент, переложив его в «j,p,q»
| | if j = 1 then begin
| | | writeln (‘сделать ход’, p, ‘-«‘, q);
| | end else begin
| | | s:=6-p-q;
| | |
| | | положить в стек тройки «j-1,s,q», «1,p,q», «j-1,p,s»
| | end;
| end;
end;

(Заметим, что сначала в стек кладется тройка, которую надо выполнять
последней.) Стек троек может быть реализован как стри
отдельных стека. (Кроме того, в паскале есть специальный тип,
называемый «запись», который может быть применен.)

8.2.2. (Сообщил А.К.Звонкин со ссылкой на Анджея Лисовского.)
Для задачи о ханойских башнях есть и другие нерекусивные
алгоритмы. Вот один из них: простаивающим стержнем (не тем, с
которого переносят, и не тем, на который переносят) должны быть
все стержни по очереди. Другое правило: поочередно перемещать
наименьшее кольцо и не наименьшее кольцо, причем наименьшее — по
кругу.

8.2.3. Использовать замену рекурсии стеком отложенных заданий
в рекурсивной программе печати десятичной записи целого числа.

Решение. Цифры добываются с конца и закладываются в стек, а
затем печатаются в обратном порядке.

8.2.4. Написать нерекурсивную программу, печатающую все
вершины двоичного дерева.

Решение. В этом случае стек отложенных заданий будет содержать
заказы двух сортов: заказ напечатать (в свое время) данную
вершину и заказ напечатать все вершины поддерева с данным корнем
(при этом nil считается корнем пустого дерева). Таким образом,
элемент стека есть пара: «тип заказа, номер вершины».
Вынимая элемент из стека, мы либо сразу исполняем его (если
это заказ первого типа) либо помещаем в стек три порожденных им
заказа — в одном из шести возможных порядков.

8.2.5. Что изменится, если требуется не печатать вершины
двоичного дерева, а подсчитать их количество?

Решение. Печатание вершины следует заменить прибавлением
единицы к счетчику. Другими словами, инвариант таков: (общее
число вершин) = (счетчик) + (сумма чисел вершин в поддеревьях,
корни которых лежат в стеке).

8.2.6. Для некоторых из шести возможных порядков возможны
упрощения, делающие ненужным хранение в стеке элементов двух видов.
Указать некоторые из них.

Решение. Если требуемый порядок таков:
корень, левое поддерево, правое поддерево,
то заказ на печатание корня можно не закладывать в стек, а выполнять
сразу.

Несколько более сложная конструкция применима для порядка
левое поддерево, корень, правое поддерево.
В этом случае все заказы в стеке, кроме самого первого (напечатать
поддерево) делятся на пары:
напечатать вершину x, напечатать правое поддерево x
(т.е. поддерево с корнем в правом сыне x). Объединив эти пары в
заказы специального вида и введя переменную для отдельного хранения
первого заказа, мы обойдемся стеком однотипных заказов.
То же самое, разумеется, верно, если поменять местами левое
и правое — получается еще два порядка.

Замечание. Другую программу печати всех вершин дерева можно
построить на основе программы обхода дерева, разобранной в соответствующей
главе. Там используется команда «вниз». Поскольку
теперешнее представление дерева с помощью массивов l и r не позволяет
найти предка заданной вершины, придется хранить список
всех вершин на пути от корня к текущей вершине. Смотри также
главу об алгоритмах на графах.

8.2.7. Написать нерекурсивный вариант программы быстрой
сортировки. Как обойтись стеком, глубина которого ограничена
C*log n, где n — число сортируемых элементов?

Решение. В стек кладутся пары «i,j», интерпретируемые как
отложенные задания на сортировку соответствующих участков массива.
Все эти заказы не пересекаются, поэтому размер стека не может
превысить n. Чтобы ограничиться стеком логарифмической глубины,
будем придерживаться такого правила: глубже в стек помещать
больший из возникающих двух заказов. Пусть f(n) — максимальная
глубина стека, которая может встретиться при сортировке
массива из не более чем n элементов таким способом. Оценим f(n)
сверху таким способом: после разбиения массива на два участка мы
сначала сортируем более короткий (храня в стеке про запас) более
длинный, при этом глубина стека не больше f(n/2)+1, затем сортируем
более длинный, так что

откуда очевидной индукцией получаем f(n) = O(log n).

8.3. Более сложные случаи рекурсии.

Пусть функция f с натуральными аргументами и значениями определена
рекурсивно условиями
f(0) = a,
f(x) = h(x, f(l(x))),
где a — некоторое число, а h и l — известные функции. Другими
словами, значение функции f в точке x выражается через значение
f в точке l(x). При этом предполагается, что для любого x в последовательности

x, l(x), l(l(x)).
рано или поздно встретится 0.
Если дополнительно известно, что l(x) » x для всех x, то
вычисление f не представляет труда: вычисляем последовательно
f(0), f(1), f(2).

8.3.1. Написать нерекурсивную программу вычисления f для
общего случая.

Решение. Для вычисления f(x) вычисляем последовательность
l(x), l(l(x)), l(l(l(x))).
до появления нуля и запоминаем ее, а затем вычисляем значения f
в точках этой последовательности, идя справа налево.

Еще более сложный случай из следующей задачи вряд ли встретится
на практике (а если и встретися, то проще рекурсию не
устранять, а оставить). Но тем не менее: пусть функция f с натуральными
аргументами и значениями определяется соотношениями
f(0) = a,
f(x) = h(x, f(l(x)), f(r(x))),
где a — некоторое число, а l, r и h — известные функции. Предполагается,
что если взять произвольное число и начать применять к
нему функции l и r в произвольном порядке, то рано или поздно
получится 0.

8.3.2. Написать нерекурсивную программу вычисления f.

Решение. Можно было бы сначала построить дерево, у которого
в корне находится x, а в сыновьях вершины i стоят l(i) и r(i) —
если только i не равно нулю, а затем вычислять значения функции,
идя от листьев к корню. Однако есть и другой способ.

«Обратной польской записью» (или «постфиксной записью») выражения
называют запись, где знак функции стоит после всех ее
аргументов, а скобки не используются. Вот несколько примеров:

f(2) 2 f
f(g(2)) 2 g f
s(2,t(7)) 2 7 t s
s(2, u(2, s(5,3)) 2 2 5 3 s u s

Постфиксная запись выражения позволяет удобно вычислять его с
помощью «стекового калькулятора». Этот калькулятор имеет стек,
который мы будем представлять себе расположенным горизонтально
(числа вынимаются и кладутся справа). При нажатии на клавишу с
числом это число кладется в стек. При нажатии на функциональную
клавишу соответствующая функция применяется к нескольким аргументам
у вершины стека. Например, если в стеке были числа
2 3 4 5 6
и нажата функциональная клавиша s, соотвтетствующая функции от
двух аргументов, то в стеке окажутся числа
2 3 4 s(5,6)

Перейдем теперь к нашей задаче. В процессе вычисления значения
функции f мы будем работать со стеком чисел, а также с последовательностью
чисел и символов «f», «l», «r», «h», которую мы будем
интерпретировать как последовательность нажатий кнопок на
стековом калькуляторе. Инвариант такой:

Cравнение цикла и рекурсии с точки зрения производительности приложений

Серия контента:

Этот контент является частью # из серии # статей: Комментарий

Этот контент является частью серии: Комментарий

Следите за выходом новых статей этой серии.

Написание кода с оптимальной производительностью

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

Рекурсия

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

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

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

5!
5 * 4!
5 * 4 * 3!
5 * 4 * 3 * 2!
5 * 4 * 3 * 2 * 1!
5 * 4 * 3 * 2 * 1

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

5!
5 * 4!
5 * 4 * 3!
5 * 4 * 3 * 2!
5 * 4 * 3 * 2 * 1!
5 * 4 * 3 * 2 * 1

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

Листинг 1. Листинг 1

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

5 * getFactorial(4)
5 * (4 * getFactorial(3))
5 * (4 * (3 * getFactorial(2)))
5 * (4 * (3 * (2 * getFactorial(1))))
5 * (4 * (3 * (2 * 1)))
120

В листинге 2 приведен пример вычисления 5! с помощью концевой рекурсии.

Листинг 2. Листинг 2

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

Листинг 3. Листинг 3

Языки программирования предоставляют циклы нескольких разных типов, очень хорошо знакомых большинству программистов. В языке программирования Java имеются циклы for, do и while. Цикл — это многократное исполнение нескольких операторов. Циклы не заносят данные в стек вызовов независимо от числа исполнений цикла. Важным отличием циклов от рекурсивных функций является тот факт, что циклы используют для подсчета числа исполнений итератор, а рекурсивные функции для определения момента выхода должны выполнять сравнение результатов. Другим важным отличием является возможность применения в циклах фильтров и прочих селекторов. Примером такой ситуации может служить цикл foreach.

Что лучше?

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

Контрольные примеры

Приведенные ниже контрольные примеры запускались в 64-разрядной среде исполнения IBM Java Runtime Environment (JRE) 7.0.4.0 (с аргументом командной строки -Xms256m -Xmx256m -Dcom.ibm.tools.attach.enable=no). Чтобы среда исполнения не тратила время на расширение и сжатие кучи, JRE запускалась с фиксированным размером кучи 256 МБ. Отключение API Attach не позволяет JRE запускать приложения-агенты (обычно используемые для мониторинга), что нормализует производительность в каждом тесте. При увеличении стека вызовов для инициализации стека и поддержания его на уровне 3 МБ использовался аргумент командной строки -Xss3m -Xssi3m.

Вычисление суммы

При суммировании чисел цикл показал значительно более высокую производительность, а концевая рекурсия оказалась быстрее головной. При увеличении стека вызовов Java до 3 МБ головная рекурсия сравнялась по скорости с концевой, но все же не смогла догнать цикл.

Рисунок 1. Рисунок 1. Вычисление суммы

Вычисление факториала

Этот примечательный пример иллюстрирует зависимость результатов от используемых операторов. При использовании простого типа данных int лучшие результаты во всех случаях получились для цикла. Применение типа int ограничивает величину результата до 32-разрядного целого числа со знаком. Для больших факториалов можно использовать тип данных BigInteger, но такая конструкция будет более затратной. Результаты применения BigInteger показали, что использование головной рекурсии в паре с концевой обеспечивает лучшее быстродействие, чем чисто концевая рекурсия или цикл.

Рисунок 2. Рисунок 2. Вычисление факториала

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

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

В задаче, получившей название Ханойская башня, даны три стрежня и диски разного размера, которые в исходном состоянии надеты на первый стержень в виде башни. Задача состоит в том, чтобы перенести башню на другой стержень, при этом запрещается класть большой диск на маленький. Эту замечательную задачу можно легко решить с помощью рекурсии за 2n — 1 ходов, где n — число дисков.

Например, возьмем четыре диска и попытаемся перенести их со стержня A на стержень C, используя стержень B для временного хранения. С помощью описанной ниже рекурсивной функции это может быть выполнено за 15 ходов. Процесс решения можно визуализировать этим апплетом. Функция вызывается (2n * 2) – 1, или 31 раз. Причина, по которой число вызовов функции не равно числу ходов, кроется в том, что для обработки ходов необходимо установить стек вызовов. В этом примере используется головная рекурсия (листинг 4).

Листинг 4. Листинг 4

Результат для четырех дисков показан в листинге 5.

Листинг 5. Листинг 5

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

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

Листинг 6. Листинг 6

Заключение

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

Рекурсия и стек

Вернёмся к функциям и изучим их более подробно.

Наша первая тема будет рекурсия.

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

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

В процессе выполнения задачи в теле функции могут быть вызваны другие функции для выполнения подзадач. Частный случай подвызова – когда функция вызывает сама себя. Это как раз и называется рекурсией.

Два способа мышления

В качестве первого примера напишем функцию pow(x, n) , которая возводит x в натуральную степень n . Иначе говоря, умножает x на само себя n раз.

Рассмотрим два способа её реализации.

Итеративный способ: цикл for :

Рекурсивный способ: упрощение задачи и вызов функцией самой себя:

Обратите внимание, что рекурсивный вариант отличается принципиально.

Когда функция pow(x, n) вызывается, исполнение делится на две ветви:

  1. Если n == 1 , тогда всё просто. Эта ветвь называется базой рекурсии, потому что сразу же приводит к очевидному результату: pow(x, 1) равно x .
  2. Мы можем представить pow(x, n) в виде: x * pow(x, n — 1) . Что в математике записывается как: x n = x * x n-1 . Эта ветвь – шаг рекурсии: мы сводим задачу к более простому действию (умножение на x ) и более простой аналогичной задаче ( pow с меньшим n ). Последующие шаги упрощают задачу всё больше и больше, пока n не достигает 1 .

Говорят, что функция pow рекурсивно вызывает саму себя до n == 1 .

Например, рекурсивный вариант вычисления pow(2, 4) состоит из шагов:

  1. pow(2, 4) = 2 * pow(2, 3)
  2. pow(2, 3) = 2 * pow(2, 2)
  3. pow(2, 2) = 2 * pow(2, 1)
  4. pow(2, 1) = 2

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

Рекурсивное решение задачи обычно короче, чем итеративное.

Используя условный оператор ? вместо if , мы можем переписать pow(x, n) , делая код функции более лаконичным, но всё ещё легко читаемым:

Общее количество вложенных вызовов (включая первый) называют глубиной рекурсии. В нашем случае она будет равна ровно n .

Максимальная глубина рекурсии ограничена движком JavaScript. Точно можно рассчитывать на 10000 вложенных вызовов, некоторые интерпретаторы допускают и больше, но для большинства из них 100000 вызовов – за пределами возможностей. Существуют автоматические оптимизации, помогающие избежать переполнения стека вызовов («оптимизация хвостовой рекурсии»), но они ещё не поддерживаются везде и работают только для простых случаев.

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

Контекст выполнения, стек

Теперь мы посмотрим, как работают рекурсивные вызовы. Для этого заглянем «под капот» функций.

Информация о процессе выполнения запущенной функции хранится в её контексте выполнения (execution context).

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

Один вызов функции имеет ровно один контекст выполнения, связанный с ним.

Когда функция производит вложенный вызов, происходит следующее:

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

Разберёмся с контекстами более подробно на примере вызова функции pow(2, 3) .

pow(2, 3)

В начале вызова pow(2, 3) контекст выполнения будет хранить переменные: x = 2, n = 3 , выполнение находится на первой строке функции.

Можно схематически изобразить это так:

Это только начало выполнения функции. Условие n == 1 ложно, поэтому выполнение идёт во вторую ветку if :


Значения переменных те же самые, но выполнение функции перешло к другой строке, актуальный контекст:

Чтобы вычислить выражение x * pow(x, n — 1) , требуется произвести запуск pow с новыми аргументами pow(2, 2) .

pow(2, 2)

Для выполнения вложенного вызова JavaScript запоминает текущий контекст выполнения в стеке контекстов выполнения.

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

  1. Текущий контекст «запоминается» на вершине стека.
  2. Создаётся новый контекст для вложенного вызова.
  3. Когда выполнение вложенного вызова заканчивается – контекст предыдущего вызова восстанавливается, и выполнение соответствующей функции продолжается.

Вид контекста в начале выполнения вложенного вызова pow(2, 2) :

Новый контекст выполнения находится на вершине стека (и выделен жирным), а предыдущие запомненные контексты – под ним.

Когда выполнение подвызова закончится, можно будет легко вернуться назад, потому что контекст сохраняет как переменные, так и точное место кода, в котором он остановился. Слово «строка» на рисунках условно, на самом деле запоминается более точное место в цепочке команд.

pow(2, 1)

Процесс повторяется: производится новый вызов в строке 5 , теперь с аргументами x=2 , n=1 .

Создаётся новый контекст выполнения, предыдущий контекст добавляется в стек:

Теперь в стеке два старых контекста и один текущий для pow(2, 1) .

Выход

При выполнении pow(2, 1) , в отличие от предыдущих запусков, условие n == 1 истинно, поэтому выполняется первая ветка условия if :

Вложенных вызовов больше нет, поэтому функция завершается, возвращая 2 .

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

Возобновляется обработка вызова pow(2, 2) . Имея результат pow(2, 1) , он может закончить свою работу x * pow(x, n — 1) , вернув 4 .

Восстанавливается контекст предыдущего вызова:

Самый внешний вызов заканчивает свою работу, его результат: pow(2, 3) = 8 .

Глубина рекурсии в данном случае составила 3.

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

Обратим внимание на требования к памяти. Рекурсия приводит к хранению всех данных для неоконченных внешних вызовов в стеке, и в данном случае это приводит к тому, что возведение в степень n хранит в памяти n различных контекстов.

Реализация возведения в степень через цикл гораздо более экономна:

Итеративный вариант функции pow использует один контекст, в котором будут последовательно меняться значения i и result . При этом объём затрачиваемой памяти небольшой, фиксированный и не зависит от n .

Любая рекурсия может быть переделана в цикл. Как правило, вариант с циклом будет эффективнее.

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

Часто код с использованием рекурсии более короткий, лёгкий для понимания и поддержки. Оптимизация требуется не везде, как правило, нам важен хороший код, поэтому она и используется.

Рекурсивные обходы

Другим отличным применением рекурсии является рекурсивный обход.

Представьте, у нас есть компания. Структура персонала может быть представлена как объект:

Другими словами, в компании есть отделы.

Отдел может состоять из массива работников. Например, в отделе sales работают 2 сотрудника: Джон и Алиса.

Или отдел может быть разделён на подотделы, например, отдел development состоит из подотделов: sites и internals . В каждом подотделе есть свой персонал.

Также возможно, что при росте подотдела он делится на подразделения (или команды).

Например, подотдел sites в будущем может быть разделён на команды siteA и siteB . И потенциально они могут быть разделены ещё. Этого нет на картинке, просто нужно иметь это в виду.

Теперь, допустим, нам нужна функция для получения суммы всех зарплат. Как мы можем это сделать?

Итеративный подход не прост, потому что структура довольно сложная. Первая идея заключается в том, чтобы сделать цикл for поверх объекта company с вложенным циклом над отделами 1-го уровня вложенности. Но затем нам нужно больше вложенных циклов для итераций над сотрудниками отделов второго уровня, таких как sites … А затем ещё один цикл по отделам 3-го уровня, которые могут появиться в будущем? Если мы поместим в код 3-4 вложенных цикла для обхода одного объекта, то это будет довольно некрасиво.

Давайте попробуем рекурсию.

Как мы видим, когда наша функция получает отдел для подсчёта суммы зарплат, есть два возможных случая:

  1. Либо это «простой» отдел с массивом – тогда мы сможем суммировать зарплаты в простом цикле.
  2. Или это объект с N подотделами – тогда мы можем сделать N рекурсивных вызовов, чтобы получить сумму для каждого из подотделов, и объединить результаты.

Случай (1), когда мы получили массив, является базой рекурсии, тривиальным случаем.

Случай (2), при получении объекта, является шагом рекурсии. Сложная задача разделяется на подзадачи для подотделов. Они могут, в свою очередь, снова разделиться на подотделы, но рано или поздно это разделение закончится, и решение сведётся к случаю (1).

Информатика. Алгоритмика. 6 класс. Звонкин А.К., Ландо С.К., Семенов А.Л.

Основная цель учебника — научить школьников алгоритмическому мышлению: умениям предусматривать и анализировать обстоятельства, планировать свои действия. Первая часть содержит объяснительный материал, описание исполнителей, примеры решения задач. Во второй части собраны и систематизированы задачи. Учебник и задачи соответствуют федеральному учебному плану по математике и информатике. Курс рассчитан на безмашинное обучение, однако существует и распространяется программное обеспечение учебника для компьютера IBM PC.

Оглавление
От авторов 6
УЧЕБНИК
Глава 1 Исполнитель и его команды
1. Волк, коза и капуста с точки зрения программиста . 8
2. Задача напоминает игру 10
3. Водолей 11
4. Удвоитель 13
5. Кузнечик 14
6. ОТКАЗ 16
7. Обозначения, языки, синтаксис —
8. Как облегчить себе программирование 20
Итоги 22
Глава 2. Процедуры, или Как делать новые команды
Итоги 26
Глава 3 Конструкция повторения
1. Солдаты и лодка 27
2. Новая конструкция 28
3. Зачем нужно слово КОНЕЦ в конце конструкции ПОВТОРИТЬ. Другие комментарии 29
4. Использование новой конструкции. Кузнечик 30
5. Использование новой конструкции. Удвоитель 32
6. Почему прописные (большие) буквы 33
7. Эффективность и сложность 34
8. Эффективный Удвоитель 35
Итоги 38
Глава 4. Условия, или Как использовать обстановку
1. Улучшенный Раздвоитель 39
2. Блок-схемы 42
3. Конструкция повторения ПОКА — ДЕЛАТЬ 45
4. Некоторые комментарии к конструкции ПОКА —ДЕЛАТЬ 47
Итоги 50
Глава 5. Робот
1. Где живет Робот 51
2. Стены —
3. Знакомство с возможностями Робота 53
4. Повторяющиеся мотивы 59
5. Задачи потруднее 65
6. Составные условия 69
7. Программы с составными условиями 71
8. Пример сложной программы 75
Итоги 77
Глава 6. Чертежник
1. Точки и векторы на плоскости 78
2. Команды Чертежника 79
3. Арифметические выражения 82
4. Разные задачи для Чертежника 84
Итоги 92
Глава 7. Черепаха
1. Где живет Черепаха и что она может делать 93
2. Повороты 94
3. Рисуем квадрат 95
4. Что легко для Черепахи и трудно для Чертежника и наоборот —
5. Что можно сделать из квадратов 97
6. Рисуем треугольник 100
7. Ленивая Черепаха помогает рисовать многоугольники и звезды 101
8. Рисуем окружность 103
9. Другие картинки —
Итоги —
Глава 8. Ханойская башня
1. Правила игры 104
2. Легенда 106
3. Рекордные результаты —
4. Программа 110
5. Решение задачи Брамы 112
6. Три отступления 114
7. Некоторые наблюдения 115
Итоги 119
Глава 9. Невозможность
Итоги 125
Глава 10. Директор строительства: краткое введение в параллельное программирование
Итоги 133
Глава 11. Рекурсия
1. Процедуры, вызывающие самих себя 134
2. Выход из рекурсии 138
3. Когда можно обойтись без рекурсии 140
4. Рекурсивный вызов через промежуточную процедуру 141 Итоги 142
ЗАДАЧНИК
Справочник по алгоритмическому языку
1. Значение истинности простых и сложных условий . . . 144
2. Конструкции —
3. Среда, системы команд и условия Исполнителей 145
A. Задачи без условий
1. Водолей 152
2. Удвоитель 155
3. Кузнечик 157
4. Переправа 166
5. Робот —
6. Чертежник 174
7. Черепаха 189
8. Ханойская башня 203
9. Директор строительства 207
Задачи с условиями
10. Удвоитель/Раздвоитель 211
11. Робот 214
B. Сложные задачи (проекты)
12. Удвоитель: построение оптимального алгоритма 222
13. Водолей: построение универсального алгоритма 225
14. Рекурсия. Сложные задачи для Робота 228
15. Ханойские башни 231
16. Кривые дракона 233
17. Директор строительства: построение универсального алгоритма 236
Структура задачника (послесловие для учителя) 240

Возможно, вам никогда не встречалось слово алгоритмика, и, наверное, вас заинтересует, что и почему вы будете изучать в этом курсе.
Алгоритмика почти то же самое, что и программирование. Но заниматься мы будем в основном не компьютерами, а специальными способами и приемами мышления. Некоторые считают, что программирование появилось с изобретением компьютеров. Это не так. Нажимание кнопок — не главный признак программирования. Самое важное в нем — это Алгоритмическое Мышление, т. е. искусство размышлять, умение планировать свои действия, способность предусматривать различные обстоятельства и поступать соответственно с ними.
Все эти умения и способности понадобились людям задолго до того, как был изготовлен первый компьютер. Само слово «алгоритм» происходит от имени средневекового ученого Мухаммеда ибн Мусы альХорезми (787—850), жившего в Средней Азии. В XIII веке, когда труды аль-Хорезми были переведены с арабского языка на латынь, его имя записали так: Algorithmus. Но, конечно, люди изобретали алгоритмы и до Мухаммеда ибн Мусы. Например, все математики знают так называемый алгоритм Евклида, а Евклид жил больше двух тысяч лет назад!
Главное, что отличает специалиста по программированию, — это умение ясно мыслить. Его указания должны быть настолько ясными, чтобы их мог понять даже компьютер. Вот такой ясности мысли мы с вами и будем учиться.
При этом мы могли бы обойтись вообще без компьютеров. Но на самом деле компьютеры оказывают огромную помощь. Ведь они не притворяются: они действительно не понимают нечетких инструкций. Именно компьютер является окончательным судьей в том, достигли ли мы полной ясности в решении задачи, или в нем еще остались какие-то туманные моменты.

О том, как читать книги в форматах pdf , djvu — см. раздел » Программы; архиваторы; форматы pdf, djvu и др. «

Книга написана по материалам занятий программированием со школь

вернуться в начало

скачать
Глава 8. Как обойтись без рекурсии.

Для универсальных языков программирования (каковым является

паскаль) рекурсия не дает ничего нового: для всякой рекурсивной

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

Мы не будем доказывать этого, а продемонстрируем некоторые при-

емы, позволяющие избавиться от рекурсии в конкретных ситуациях.

Зачем это нужно? Ответ прагматика мог бы быть таким: во

многих компьютерах (в том числе, к сожалению, и в современных,

использующих так называемые RISC-процессоры), рекурсивные прог-

раммы в несколько раз медленнее соответствующих нерекурсивных

программ. Еще один возможный ответ: в некоторых языках програм-

мирования рекурсивные программы запрещены. А главное, при удале-

нии рекурсии возникают изящные и поучительные конструкции.

8.1. Таблица значений (динамическое программирование)

8.1.1. Следующая рекурсивная процедура вычисляет числа со-

четаний (биномиальные коэффициенты). Написать эквивалентную не-

function C(n,k: integer):integer;

8.1.3. Дан выпуклый n-угольник (заданный координатами своих

вершин в порядке обхода). Его разрезают на треугольники диагона-

лями, для чего необходимо n-2 диагонали (докажите индукцией по

n). Стоимостью разрезания назовем сумму длин всех использованных

диагоналей. Найти минимальную стоимость разрезания. Число

действий должно быть ограничено некоторым многочленом от n. (Пе-

ребор не подходит, так как число вариантов не ограничено многоч-

Решение. Будем считать, что вершины пронумерованы от 1 до n

и идут по часовой стрелке. Пусть k, l — номера вершин, причем

l>k. Через A(k,l) обозначим многоугольник, отрезаемый от нашего

хордой k—l. (Эта хорда разрезает многоугольник на 2, один из

которых включает сторону 1—n; через A(k,l) мы обозначаем дру-

гой.) Исходный многоугольник естественно обозначить A(1,n). При

l=k+1 получается «двуугольник» с совпадающими сторонами.

Через a(k,l) обозначим стоимость разрезания многоугольника

A(k,l) диагоналями на треугольники. Напишем рекуррентную формулу

для a(k,l). При l=k+1 получается двуугольник, и мы полагаем

a(k,l)=0. При l=k+2 получается треугольник, и в этом случае так-

же a(k,l)=0. Пусть l > k+2. Хорда k—l является стороной много-

угольника A(k,l) и, следовательно, стороной одного из тре-

угольников, на которые он разрезан. Противоположной вершиной i

этого треугольника может быть любая из вершин k+1. l-1, и ми-

нимальная стоимость разрезания может быть вычислена как

по всем i=k+1. i=l-1. При этом надо учесть, что при q=p+1

хорда p—q — не хорда, а сторона, и ее длину надо считать равной

0 (по стороне разрез не проводится).

Составив таблицу для a(k,l) и заполняя ее в порядке возрас-

тания числа вершин (равного l-k+1), мы получаем программу, ис-

пользующую память порядка n*n и время порядка n*n*n (однократное

применение рекуррентной формулы требует выбора минимума из не

более чем n чисел).

8.1.4. Матрицей размера m*n называется прямоугольная табли-

ца из m строк и n столбцов, заполненная числами. Матрицу размера

m*n можно умножить на матрицу размера n*k (ширина левого сомно-

жителя должна равняться высоте правого), и получается матрица

размером m*k. Ценой такого умножения будем считать произведение

m*n*k (таково число умножений, которые нужно выполнить при стан-

дартном способе умножения — но сейчас это нам не важно). Умноже-

ние матриц ассоциативно, поэтому произведение s матриц можно вы-

числять в разном порядке. Для каждого порядка подсчитаем суммар-

ную цену всех матричных умножений. Найти минимальную цену вычис-

ления произведения, если известны размеры всех матриц. Число

действий должно быть ограничено многочленом от числа матриц.

Пример. Матрицы размером 2*3, 3*4, 4*5 можно перемножать

двумя способами. В первом цена равна 2*3*4 + 2*4*5 = 24 + 40 =

64, во втором цена равна 3*4*5 + 2*3*5 = 90.

Решение. Представим себе, что первая матрица написана на

отрезке [0,1], вторая — на отрезке [1,2]. s-ая — на отрезке

[s-1,s]. Матрицы на отрезках [i-1,i] и [i,i+1] имеют общий раз-

мер, позволяющих их перемножить. Обозначим его через d[i]. Таким

образом, исходным данным в задаче является массив d[0]..d[s].

Через a(i,j) обозначим минимальную цену вычисления произве-

дения матриц на участке [i,j] (при 0 ‘, n);

| | writeln (‘сделать ход ‘, m, ‘->’, n);

Видно, что задача «переложить i верхних дисков с m-го стержня на

n-ый» сводится к трем задачам того же типа: двум задачам с i-1

дисками и к одной задаче с единственным диском. Занимаясь этими

задачами, важно не позабыть, что ещё осталось сделать.

Для этой цели заведем стек отложенных заданий, элементами

которого будут тройки . Каждая такая тройка интерпретиру-

ется как заказ «переложить i верхних дисков с m-го стержня на

n-ый». Заказы упорядочены в соответствии с требуемым порядком их

выполнения: самый срочный — вершина стека. Получаем такую прог-

procedure move(i,m,n: integer);

| сделать стек заказов пустым

| положить в стек тройку

| while стек непуст do begin

| | удалить верхний элемент, переложив его в

| | if j = 1 then begin

| | | writeln (‘сделать ход’, p, ‘->’, q);

| | | положить в стек тройки , ,


(Заметим, что первой в стек кладётся тройка, которую надо выпол-

нять последней.) Стек троек может быть реализован как стри от-

дельных стека. (Кроме того, в паскале есть специальный тип, на-

зываемый «запись», который может быть применён.)

8.2.2. (Сообщил А.К.Звонкин со ссылкой на Анджея Лисовско-

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

алгоритмы. Вот один из них: простаивающим стержнем (не тем, с

которого переносят, и не тем, на который переносят) должны быть

все стержни по очереди. Другое правило: поочерёдно перемещать

наименьшее кольцо и не наименьшее кольцо, причем наименьшее — по

8.2.3. Использовать замену рекурсии стеком отложенных зада-

ний в рекурсивной программе печати десятичной записи целого чис-

Решение. Цифры добываются с конца и закладываются в стек, а

затем печатаются в обратном порядке.

8.2.4. Написать нерекурсивную программу, печатающую все

вершины двоичного дерева.

Решение. В этом случае стек отложенных заданий будет содер-

жать заказы двух сортов: «напечатать (в свое время) данную вер-

шину» и «напечатать все вершины поддерева с данным корнем» (при

этом nil считается корнем пустого дерева). Таким образом, эле-

мент стека есть пара: .

Вынимая элемент из стека, мы либо сразу исполняем его (если

это заказ первого типа) либо помещаем в стек три порожденных им

заказа — в одном из шести возможных порядков.

8.2.5. Что изменится, если требуется не печатать вершины

двоичного дерева, а подсчитать их количество?

Решение. Печатание вершины следует заменить прибавлением

единицы к счетчику. Другими словами, инвариант таков: (общее

число вершин) = (счетчик) + (сумма чисел вершин в поддеревьях,

корни которых лежат в стеке).

8.2.6. Для некоторых из шести возможных порядков возможны

упрощения, делающие ненужным хранение в стеке элементов двух ви-

дов. Указать некоторые из них.

Решение. Если требуемый порядок таков:

корень, левое поддерево, правое поддерево,

то заказ на печатание корня можно не закладывать в стек, а вы-

Несколько более сложная конструкция применима для порядка

левое поддерево, корень, правое поддерево.

В этом случае все заказы в стеке, кроме самого первого (напеча-

тать поддерево) делятся на пары:

напечатать вершину x, напечатать правое поддерево x

(т.е. поддерево с корнем в правом сыне x). Объединив эти пары в

заказы специального вида и введя переменную для отдельного хра-

нения первого заказа, мы обойдемся стеком однотипных заказов.

То же самое, разумеется, верно, если поменять местами левое

и правое — получается еще два порядка.

Замечание. Другую программу печати всех вершин дерева можно

построить на основе программы обхода дерева, разобранной в соот-

ветствующей главе. Там используется команда «вниз». Поскольку

теперешнее представление дерева с помощью массивов l и r не поз-

воляет найти предка заданной вершины, придется хранить список

всех вершин на пути от корня к текущей вершине. Cмотри также

главу об алгоритмах на графах.

8.2.7. Написать нерекурсивный вариант программы быстрой

сортировки. Как обойтись стеком, глубина которого ограничена

C*log n, где n — число сортируемых элементов?

Решение. В стек кладутся пары , интерпретируемые как

отложенные задания на сортировку соответствующих участков масси-

ва. Все эти заказы не пересекаются, поэтому размер стека не мо-

жет превысить n. Чтобы ограничиться стеком логарифмической глу-

бины, будем придерживаться такого правила: глубже в стек поме-

щать больший из возникающих двух заказов. Пусть f(n) — макси-

мальная глубина стека, которая может встретиться при сортировке

массива из не более чем n элементов таким способом. Оценим f(n)

сверху таким способом: после разбиения массива на два участка мы

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

про запас), при этом глубина стека не больше f(n/2)+1, затем

сортируем более длинный, так что

| for s := 1 to n do begin

| | for i := 1 to n do begin

| | | if y[s] > x[i]+a[i][s] then begin

| for i := 1 to n do begin x[s] := y[s]; end;

Приведенный алгоритм называют алгоритмом динамического програм-

мирования, или алгоритмом Форда — Беллмана.

9.1.3. Доказать, что программа останется правильной, если

не заводить массива y, а производить изменения в самом массиве x

(заменив в программе все вхождения буквы y на x и затем удалить

ставшие лишними строки).

Решение. Инвариант будет таков:

МинСт(1,i,n) j для ВСЕХ пар i,j (а не только при i=1), а можно сокра-

тить время работы до O(n в степени 2). Правда, в последнем слу-

чае нам потребуется, чтобы все цены a[i][j] были неотрицательны.

9.1.4. Найти наименьшую стоимость проезда i->j для всех i,j

за время O(n в степени 3).

Решение. Для k = 0..n через А(i,j,k) обозначим наименьшую

стоимость маршрута из i в j, если в качестве пересадочных разре-

шено использовать только пункты с номерами не больше k. Тогда

(два варианта соответствуют неиспользованию и использованию

пункта k+1 в качестве пересадочного; отметим, что в нем незачем

бывать более одного раза).

Этот алгоритм называют алгоритмом Флойда.

9.1.5. Известны, что все цены неотрицательны. Найти на-

именьшую стоимость проезда 1->i для всех i=1..n за время O(n в

Решение. В процессе работы алгоритма некоторые города будут

выделенными (в начале — только город 1, в конце — все). При

для каждого выделенного города i хранится наименьшая сто-

имость пути 1->i; при этом известно, что минимум достигается на

пути, проходящем только через выделенные города;

для каждого невыделенного города i хранится наименьшая сто-

имость пути 1->i, в котором в качестве промежуточных используют-

ся только выделенные города.

Множество выделенных городов расширяется на основании сле-

дующего замечания: если среди всех невыделенных городов взять

тот, для которого хранимое число минимально, то это число явля-

ется истинной наименьшей стоимостью. В самом деле, пусть есть

более короткий путь. Рассмотрим первый невыделенный город на

этом пути — уже до него путь длиннее! (Здесь существенна неотри-

Добавив выбранный город к выделенным, мы должны скорректи-

ровать информацию, хранимую для невыделенных городов. При этом

достаточно учесть лишь пути, в которых новый город является пос-

ледним пунктом пересадки, а это легко сделать, так как минималь-

ную стоимость проезда в новый город мы уже знаем.

При самом бесхитростном способе хранения множества выделен-

ных городов (в булевском векторе) добавление одного города к

числу выделенных требует времени O(n).

Этот алгоритм называют алгоритмом Дейкстры.

Отыскание кратчайшего пути имеет естественную интерпретацию

в терминах матриц. Пусть A — матрица цен одной авиакомпании, а B

— матрица цен другой. Пусть мы хотим лететь с одной пересадкой,

причем сначала самолетом компании A, а затем — компании B.

Сколько нам придется заплатить, чтобы попасть из города i в го-

9.1.6. Доказать, что эта матрица вычисляется по обычной

формуле для произведения матриц, только вместо суммы надо брать

минимум, а вместо умножения — сумму.

9.1.7. Доказать, что таким образом определенное произведе-

ние матриц ассоциативно.

9.1.8. Доказать, что задача о кратчайших путях эквивалентна

вычислению «бесконечной степени» матрицы цен A: в последова-

тельности A, A*A, A*A*A. все элементы, начиная с некоторого,

равны искомой матрице стоимостей кратчайших путей. (Если нет от-

9.1.9. Начиная с какого элемента можно гарантировать ра-

венство в предыдущей задаче?

Обычное (не модифицированное) умножение матриц тоже может

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

есть не все рейсы (как раньше), а только некоторые, a[i][j] рав-

но 1, если рейс есть, и 0, если рейса нет. Возведем матрицу a

(обычным образом) в степень k и посмотрим на ее i-j-ый элемент.

9.1.10. Чему он равен?

Ответ. Числу различных способов попасть из i в j за k

рейсов (с k-1 пересадками).


Случай, когда есть не все рейсы, можно свести к исходному,

введя фиктивные рейсы с бесконечно большой (или достаточно

большой) стоимостью. Тем не менее возникает такой вопрос. Число

реальных рейсов может быть существенно меньше n*n, поэтому инте-

ресны алгоритмы, которые работают эффективно в такой ситуации.

Исходные данные естественно представлять тогда в такой форме:

для каждого города известно число выходящих из него рейсов, их

пункты назначения и цены.

9.1.11. Доказать, что алгоритм Дейкстры можно модифициро-

вать так, чтобы для n городов и m рейсов (всего) он требовал не

более C*(n+k)*log n операций.

Указание. Что надо сделать на каждом шаге? Выбрать невыде-

ленный город с минимальной стоимостью и скорректировать цены для

всех городов, в которые из него есть маршруты. Если бы кто-то

сообщал нам, для какого города стоимость минимальна, то хватило

бы C*(n+m) действий. А поддержание сведений о том, какой элемент

в массиве минимален (см. задачу 6.4.1 в главе о типах данных)

обходится еще в множитель log n.

9.2. Связные компоненты, поиск в глубину и ширину

Наиболее простой случай задачи о кратчайших путях — если

все цены равны 0 или бесконечны. Другими словами, мы интересуем-

ся возможностью попасть из i в j, но за ценой не постоим. В дру-

гих терминах: мы имеем ориентированный граф (картинку из точек,

некоторые из которых соединены стрелками) и нас интересуют вер-

шины, доступные из данной.

Для этого случая задачи о кратчайших путях приведенные в

предыдущем разделе алгоритмы — не наилучшие. В самом деле, более

быстрая рекурсивная программа решения этой задачи приведена в

главе 7 (Рекурсия), а нерекурсивная — в главе 6 (Типы данных).

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

вершины, доступные из данной, но перечислить их в определенном

порядке. Два популярных случая — поиск в ширину и в глубину.

Поиск в ширину: надо перечислить все вершины ориентирован-

ного графа, доступные из данной, в порядке увеличения длины пути

от нее. (Тем самым мы решим задачу о кратчайших путях, кода цены

ребер равны 1 или бесконечны.)

9.2.1. Придумать алгоритм решения этой задачи с числом

действий не более C*(число ребер, выходящих из интересующих нас

Решение. Эта задача рассматривалась в главе 6 (Типы дан-

ных), 6.3.7 — 6.3.8. Здесь мы приведём подробное решение. Пусть

num[i] — количество ребер, выходящих из i, out[i][1].

out[i][num[i]] — вершины, куда ведут ребра. Вот программа, при-

procedure Доступные (i: integer);

| var X: подмножество 1..n;

| P: подмножество 1..n;

| . сделать X, P пустыми;

| . добавить i к X, P;

| (2) напечатаны только доступные из i вершины;

| (3) X — подмножество P;

| (4) все напечатанные вершины, из которых выходит

| ребро в ненапечатанную вершину, принадлежат X>

| while X непусто do begin

| | . взять какой-нибудь элемент X в v;

| | for k := 1 to num [v] do begin

| | | if w не принадлежит P then begin

Тогда нам было безразлично, какой именно элемент множества X вы-

бирается. Если мы будем считать X очередью (первым пришел — пер-

вым ушел), то эта программа напечатает все вершины, доступные из

i, в порядке возрастания их расстояния от i (числа ребер на

кратчайшем пути из i). Докажем это.

Обозначим через V(k) множество всех вершин, расстояние ко-

торых от i (в описанном смысле) равно k. Имеет место такое соот-

V(k+1) = (концы ребер с началами в V(k))-V(0)-V(1)-. -V(k)

(знак «-» обозначает вычитание множеств). Докажем, что для любо-

го k=0,1,2. в ходе работы программы будет такой момент (после

очередной итерации цикла while), когда

в очереди стоят все элементы V(k) и только они

напечатаны все элементы V(0). V(k)

(Для k=0 — это состояние перед циклом.) Рассуждая по индукции,

предположим, что в очереди скопились все элементы V(k). Они бу-

дут просматриваться в цикле, пока не кончатся (поскольку новые

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

Концы ведущих из них ребер, если они уже не напечатаны, печата-

ются и ставятся в очередь — то есть всё как в записанном выше

соотношении для V(k+1). Так что когда все старые элементы кон-

чатся, в очереди будут стоять все элементы V(k+1).

Поиск в глубину.

Рассматривая поиск в глубину, удобно представлять себе ори-

ентированный граф как образ дерева. Более точно, пусть есть ори-

ентированный граф, одна из вершин которого выделена. Будем пред-

полагать, что все вершины доступны из выделенной по ориентиро-

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

«универсальным накрытием» нашего графа. Его корнем будет выде-

ленная вершина графа. Из корня выходят те же стрелки, что и в

графе — их концы будут сыновьями корня. Из них в дереве выходят

те же стрелки, что и в графе и так далее. Разница между графом и

деревом в том, что пути в графе, ведущие в одну и ту же вершину,

в дереве «расклеены». В других терминах: вершина дерева — это

путь в графе, выходящий из корня. Ее сыновья — это пути, продол-

женные на одно ребро. Заметим, что дерево бесконечно, если в

графе есть ориентированные циклы.

Имеется естественное отображение дерева в граф (вершин в

вершины). При этом каждая вершина графа имеет столько прообра-

зов, сколько путей в нее ведет. Поэтому обход дерева (посещение

его вершин в том или ином порядке) одновременно является и обхо-

дом графа — только каждая вершина посещается многократно.

Будем предполагать, что для каждой вершины графа выходящие

из неё ребра упорядочены (например, пронумерованы). Тем самым

для каждой вершины дерева выходящие из неё ребра также упорядо-

чены. Будем обходить дерево так: сначала корень, а потом подде-

ревья (в порядке ведущих в них ребер). Такой обход дерева

рассматривался нами в главе о рекурсии. Ему соответствует обход

графа. Если выкинуть из этого обхода повторные посещения уже по-

сещенных вершин, то получится то, что называется «поиск в глуби-

Другими словами, на путях, выходящих из выделенной вершины,

введем порядок: путь предшествует своему продолжению; если два

пути расходятся в некоторой вершине, то меньшим считается тот,

который выходит из нее по меньшему ребру. Вершины теперь упоря-

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

Обход вершин графа в указанном порядке называется поиском в глу-

9.2.2. Написать программу поиска в глубину.

Указание. Возьмем программу обхода дерева (корень — левое

поддерево — правое поддерево) из главы о рекурсии или из гравы

об устранении рекурсии и используем ее применительно к обсто-

ятельствам. Главное изменение: не надо посещать вершины повтор-

но. Так что если мы попали в уже посещенную вершину, то можно с

ней ничего не делать. (Если путь не минимален среди ведущих в

данную вершину, то и все его продолжения не минимальны — их

просматривать не надо).

Замечание. Напомним, что в главе 8 упоминались две возмож-

ности устранения рекурсии в программе обхода дерева (замечание

после задачи 8.2.6). Оба варианта можно использовать для поиска

Поиск в глубину лежит в основе многих алгоритмов на графах,

порой в несколько модифицированном виде.

9.2.3. Неориентированный граф называется двудольным, если

его вершины можно раскрасить в два цвета так, что концы любого

ребра — разного цвета. Составить алгоритм проверки, является ли

заданный граф двудольным, в котором число действий не провосхо-

дит C*(число ребер + число вершин).

Указание. (а) Каждую связную компоненту можно раскрашивать

отдельно. (б) Выбрав цвет одной вершины и обходя ее связную ком-

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

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

ширину или в глубину.

9.2.4. Составить нерекурсивный алгоритм топологической сор-

тировки ориентированного графа без циклов. (См. задачу 7.4.2 в

главе о рекурсии.)

Решение. Предположим, что граф имеет вершины с номерами

1..n, для каждой вершины i известно число num[i] выходящих из


нее ребер и номера вершин dest[i][1]. dest[i][num[i]], в ко-

торые эти ребра ведут. Будем условно считать, что ребра перечис-

лены «слева направо»: левее то ребро, у которого номер меньше.

Нам надо напечатать все вершины в таком порядке, чтобы конец лю-

бого ребра был напечатан перед его началом. Мы предполагаем, что

в графе нет ориентированных циклов — иначе такое невозможно.

Для начала добавим к графу вершину 0, из которой ребра ве-

дут в вершины 1. n. Если ее удастся напечатать с соблюдением

правил, то тем самым все вершины будут напечатаны.

Алгоритм хранит путь, выходящий из нулевой вершины и иду-

щий по ребрам графа. Переменная l отводится для длины этого пу-

ти. Путь образован вершинами vert[1]. vert[l] и ребрами,

имеющими номера edge[1]. edge[l]. Номер edge[s] относится к ну-

мерации ребер, выходящих из вершины vert[s]. Тем самым для всех

Рекурсия, рекурсивный процесс и итеративный процесс

Рекурсия vs. какой-то процесс

Давайте для начала явно отметим отличие рекурсии (в общем смысле) от процесса. Эти понятия никак не связаны. Рекурсия — просто абстрактная концепция, которую можно наблюдать в природе, которая используется в математике и в других областях. Такая же абстрактная, как, например, музыкальная гармония.

пример рекурсии: художник рисует картину, в которой он рисует картину, в которой он рисует картину.

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

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

Если продолжить аналогию с музыкальной гармонией, то можно подумать про фортепиано. При написании музыки можно использовать эту концепцию — «гармонию звуков». И можно придумать разные способы: рассчитывать частоты звуков (ноты) математическими формулами или рассчитывать правильные расстояния между клавишами. Я в детстве научился находить правильные расстояния между клавишами на фортепиано, и получал гармоничные комбинации звуков, но понятия не имел, что это за ноты. А профессиональный музыкант знает теорию и подбирает гармонию другими методами. В любом случае, гармония есть гармония, эта концепция не меняется, меняются лишь способы ее использования.

В чем отличие итеративного процесса от рекурсивного?

Главная фишка в аккумуляторе или, иными словами, в запоминании.

Рекурсивный процесс постоянно говорит «я это запомню и потом посчитаю» на каждом шаге рекурсии. «Потом» наступает в самом конце.

  • Когда рекурсивный процесс считает факториал 6, то ему нужно запомнить 5 чисел чтобы посчитать их в самом конце, когда уже никуда не деться и рекурсивно двигаться вниз больше нельзя.
  • Когда мы находимся в очередном вызове функции, то где-то снаружи этого вызова в памяти хранятся эти запомненные числа.

тут прямо физически видно, как растет использование памяти: процессу нужно запоминать все больше и больше чисел

Рекурсивный процесс — это процесс с отложенным вычислением.

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

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

тут видно, что использование памяти не растет

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

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

Tail call optimization

Отмотаем назад и рассмотрим во взаимосвязи два утверждения относительно рекурсивных функций, использующих итеративный процесс:

  • Во-первых, такие функции являются рекурсивными. Это значит, что для каждого (очередного) рекурсивного вызова в стек вызовов записывается вся информация, связанная с этим конкретным вызовом (параметры функции и её локальные переменные, адрес возврата в точку вызова). Т.е. выделяется дополнительная область памяти (лексический контекст функции, область видимости), обслуживающая данный рекурсивный вызов, а так как это стек вызовов, то контексты предыдущих рекурсивных вызовов также продолжают занимать память. Достижение большой глубины рекурсии (или же если она вовсе является бесконечной, т.е. не достигается терминальное условие выхода из рекурсии) приводит к переполнению стека (ведь он ограничен в размерах) и аварийному завершению всей программы.
  • Во-вторых, в контексте каждого очередного рекурсивного вызова такой функции хранится вся необходимая информация для его успешного выполнения. Он самодостаточен и никак не зависит от предыдущих контекстов (помните, «этот чувак ничего не откладывает на потом, на вечер пятницы. «?!). В наших практиках на Хекслете мы реализовывали такое поведения благодаря использованию аккумулятора acc , передающегося в качестве аргумента из одного вызова в другой и накапливающего в себе результат вычисления необходимого значения. Получается, что, грубо говоря, на каком бы по уровню вложенности рекурсивном вызове мы не находились, все предыдущие уже не имеют значения и являются » бесполезной обузой», нагружающей память. В т.ч. это распространяется и на самый последний рекурсивный вызов (где срабатывает терминальное условие), который сразу готов вернуть готовое вычисленное значение из функции, ему не нужны для этого предыдущие контексты в стеке.

Отсюда напрашивается вопрос, как использовать рассмотренные преимущества итеративного процесса и одновременно избавиться от недостатка рекурсивных функций, т.е. от неумолимого роста использования памяти. И сразу же нарисовывается ответ — избавить процесс от заполнения стека «ненужными» контекстами предыдущих вызовов и обеспечить прямой возврат из функции при достижении терминального условия. Для этого служит так называемая Tail call optimization, или оптимизация хвостовой рекурсии (рассмотренный выше итеративный процесс как раз можно отнести к хвостовой рекурсии). Благодаря оптимизации состояния стека, она придаёт итеративному процессу вид «плоской» итерации (см. картинку выше), исключается его переполнение из-за большой глубины рекурсии.

Хвостовая рекурсия (и её оптимизация) широко используется при написании программ на функциональных языках программирования.

Персональная страничка
Диканева Тараса
Викторовича

Рекурсия и рекурсивные алгоритмы

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

Содержание

1. Сущность рекурсии

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

Пример рекурсивной процедуры:

Рассмотрим, что произойдет, если в основной программе поставить вызов, например, вида Rec(3). Ниже представлена блок-схема, показывающая последовательность выполнения операторов.

Рис. 1. Блок схема работы рекурсивной процедуры.

Процедура Rec вызывается с параметром a = 3. В ней содержится вызов процедуры Rec с параметром a = 2. Предыдущий вызов еще не завершился, поэтому можете представить себе, что создается еще одна процедура и до окончания ее работы первая свою работу не заканчивает. Процесс вызова заканчивается, когда параметр a = 0. В этот момент одновременно выполняются 4 экземпляра процедуры. Количество одновременно выполняемых процедур называют глубиной рекурсии.

Четвертая вызванная процедура (Rec(0)) напечатает число 0 и закончит свою работу. После этого управление возвращается к процедуре, которая ее вызвала (Rec(1)) и печатается число 1. И так далее пока не завершатся все процедуры. Результатом исходного вызова будет печать четырех чисел: 0, 1, 2, 3.

Еще один визуальный образ происходящего представлен на рис. 2.

Рис. 2. Выполнение процедуры Rec с параметром 3 состоит из выполнения процедуры Rec с параметром 2 и печати числа 3. В свою очередь выполнение процедуры Rec с параметром 2 состоит из выполнения процедуры Rec с параметром 1 и печати числа 2. И т. д.

В качестве самостоятельного упражнения подумайте, что получится при вызове Rec(4). Также подумайте, что получится при вызове описанной ниже процедуры Rec2(4), где операторы поменялись местами.

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

2. Сложная рекурсия

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

Опережающее описание процедуры B позволяет вызывать ее из процедуры A. Опережающее описание процедуры A в данном примере не требуется и добавлено из эстетических соображений.

Если обычную рекурсию можно уподобить уроборосу (рис. 3), то образ сложной рекурсии можно почерпнуть из известного детского стихотворения, где «Волки с перепуга, скушали друг друга». Представьте себе двух съевших друг друга волков, и вы поймете сложную рекурсию.

Рис. 3. Уроборос – змей, пожирающий свой хвост. Рисунок из алхимического трактата «Synosius» Теодора Пелеканоса (1478г).

Рис. 4. Сложная рекурсия.

3. Имитация работы цикла с помощью рекурсии

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

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

Пример 1.

Результатом вызова вида LoopImitation(1, 10) станет десятикратное выполнение инструкций с изменением счетчика от 1 до 10. В данном случае будет напечатано:

Hello N 1
Hello N 2

Hello N 10

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

Можно поменять местами рекурсивный вызов и подлежащие повторению инструкции, как в следующем примере.

Пример 2.

В этом случае, прежде чем начнут выполняться инструкции, произойдет рекурсивный вызов процедуры. Новый экземпляр процедуры также, прежде всего, вызовет еще один экземпляр и так далее, пока не дойдем до максимального значения счетчика. Только после этого последняя из вызванных процедур выполнит свои инструкции, затем выполнит свои инструкции предпоследняя и т.д. Результатом вызова LoopImitation2(1, 10) будет печать приветствий в обратном порядке:

Hello N 10

Hello N 1

Если представить себе цепочку из рекурсивно вызванных процедур, то в примере 1 мы проходим ее от раньше вызванных процедур к более поздним. В примере 2 наоборот от более поздних к ранним.

Наконец, рекурсивный вызов можно расположить между двумя блоками инструкций. Например:

Здесь сначала последовательно выполнятся инструкции из первого блока затем в обратном порядке инструкции второго блока. При вызове LoopImitation3(1, 10) получим:

Hello N 1

Hello N 10
Hello N 10

Hello N 1

Потребуется сразу два цикла, чтобы сделать то же самое без рекурсии.

Тем, что выполнение частей одной и той же процедуры разнесено по времени можно воспользоваться. Например:

Пример 3: Перевод числа в двоичную систему.

Получение цифр двоичного числа, как известно, происходит с помощью деления с остатком на основание системы счисления 2. Если есть число , то его последняя цифра в его двоичном представлении равна

Взяв же целую часть от деления на 2:

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

Проблема здесь в том, что цифры двоичного представления вычисляются в обратном порядке (сначала последние). Чтобы напечатать число в нормальном виде придется запомнить все цифры в элементах массива и выводить в отдельном цикле.

С помощью рекурсии нетрудно добиться вывода в правильном порядке без массива и второго цикла. А именно:

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

4. Рекуррентные соотношения. Рекурсия и итерация

Говорят, что последовательность векторов задана рекуррентным соотношением, если задан начальный вектор и функциональная зависимость последующего вектора от предыдущего

Простым примером величины, вычисляемой с помощью рекуррентных соотношений, является факториал

Очередной факториал можно вычислить по предыдущему как:

Введя обозначение , получим соотношение:

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

Каждое такое обновление (x := x * i) называется итерацией, а процесс повторения итераций – итерированием.

Обратим, однако, внимание, что соотношение (1) является чисто рекурсивным определением последовательности и вычисление n-го элемента есть на самом деле многократное взятие функции f от самой себя:

В частности для факториала можно написать:

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

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

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

При «лобовом» подходе можно написать:

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

На самом деле, приведенный пример учит нас не КОГДА рекурсию не следует использовать, а тому КАК ее не следует использовать. В конце концов, если существует быстрое итерационное (на базе циклов) решение, то тот же цикл можно реализовать с помощью рекурсивной процедуры или функции. Например:

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

Любые рекурсивные процедуры и функции, содержащие всего один рекурсивный вызов самих себя, легко заменяются итерационными циклами. Чтобы получить что-то, не имеющее простого нерекурсивного аналога, следует обратиться к процедурам и функциям, вызывающим себя два и более раз. В этом случае множество вызываемых процедур образует уже не цепочку, как на рис. 1, а целое дерево. Существуют широкие классы задач, когда вычислительный процесс должен быть организован именно таким образом. Как раз для них рекурсия будет наиболее простым и естественным способом решения.

5. Деревья

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

5.1. Основные определения. Способы изображения деревьев

Определение: Деревом будем называть конечное множество T, состоящее из одного или более узлов, таких что:
а) Имеется один специальный узел, называемый корнем данного дерева.
б) Остальные узлы (исключая корень) содержатся в попарно непересекающихся подмножествах , каждое из которых в свою очередь является деревом. Деревья называются поддеревьями данного дерева.

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

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

Узлы, не содержащие поддеревьев, называются концевыми узлами или листьями. Множество не пересекающихся деревьев называется лесом. Например, лес образуют поддеревья, исходящие из одного узла.

Графически дерево можно изобразить и некоторыми другими способами. Некоторые из них представлены на рис. 4. Согласно определению дерево представляет собой систему вложенных множеств, где эти множества или не пересекаются или полностью содержатся одно в другом. Такие множества можно изобразить как области на плоскости (рис. 4а). На рис. 4б вложенные множества располагаются не на плоскости, а вытянуты в одну линию. Рис. 4б также можно рассматривать как схему некоторой алгебраической формулы, содержащей вложенные скобки. Рис. 4в дает еще один популярный способ изображения древовидной структуры в виде уступчатого списка.

Рис. 4. Другие способы изображения древовидных структур: (а) вложенные множества; (б) вложенные скобки; (в) уступчатый список.

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

Также можно провести аналогию между уступчатым списком и внешним видом оглавлений в книгах, где разделы содержат подразделы, те в свою очередь поподразделы и т.д. Традиционный способ нумерации таких разделов (раздел 1, подразделы 1.1 и 1.2, подподраздел 1.1.2 и т.п.) называется десятичной системой Дьюи. В применении к дереву на рис. 3 и 4 эта система даст:

1. A; 1.1 B; 1.2 C; 1.2.1 D; 1.2.2 E; 1.2.3 F; 1.2.3.1 G;

5.2. Прохождение деревьев

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

Алгоритм обхода в прямом порядке:

  • Попасть в корень,
  • Пройти все поддеревья слева на право в прямом порядке.

Данный алгоритм рекурсивен, так как прохождение дерева содержит прохождение поддеревьев, а они в свою очередь проходятся по тому же алгоритму.

В частности для дерева на рис. 3 и 4 прямой обход дает последовательность узлов: A, B, C, D, E, F, G.

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

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

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

Алгоритм обхода в обратном порядке:

  • Пройти левое поддерево,
  • Попасть в корень,
  • Пройти следующее за левым поддерево.
  • Попасть в корень,
  • и т.д пока не будет пройдено крайнее правое поддерево.

То есть проходятся все поддеревья слева на право, а возвращение в корень располагается между этими прохождениями. Для дерева на рис. 3 и 4 это дает последовательность узлов: B, A, D, C, E, G, F.

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

Алгоритм обхода в концевом порядке:

  • Пройти все поддеревья слева на право,
  • Попасть в корень.

Для дерева на рис. 3 и 4 это даст последовательность узлов: B, D, E, G, F, C, A.

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

5.3. Представление дерева в памяти компьютера

Если некоторая информация располагается в узлах дерева, то для ее хранения можно использовать соответствующую динамическую структуру данных. На Паскале это делается с помощью переменной типа запись (record), содержащей указатели на поддеревья того же типа. Например, бинарное дерево, где в каждом узле содержится целое число можно сохранить с помощью переменной типа PTree, который описан ниже:

Каждый узел имеет тип PTree. Это указатель, то есть каждый узел необходимо создавать, вызывая для него процедуру New. Если узел является концевым, то его полям LeftSubTree и RightSubTree присваивается значение nil. В противном случае узлы LeftSubTree и RightSubTree также создаются процедурой New.

Схематично одна такая запись изображена на рис. 5.

Рис. 5. Схематичное изображение записи типа TTree. Запись имеет три поля: Inf – некоторое число, LeftSubTree и RightSubTree – указатели на записи того же типа TTree.


Пример дерева, составленного из таких записей, показан на рисунке 6.

Рис. 6. Дерево, составленное из записей типа TTree. Каждая запись хранит число и два указателя, которые могут содержать либо nil, либо адреса других записей того же типа.

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

6. Примеры рекурсивных алгоритмов

6.1. Рисование дерева

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

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

Пример такой процедуры, написанный на Delphi, представлен ниже:

Для получения рис. 6 эта процедура была вызвана со следующими параметрами:

Заметим, что рисование осуществляется до рекурсивных вызовов, то есть дерево рисуется в прямом порядке.

6.2. Ханойские башни

Согласно легенде в Великом храме города Бенарас, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времен монахи этого монастыря провинились перед богом Брамой. Разгневанный, Брама воздвиг три высоких стержня и на один из них поместил 64 диска из чистого золота, причем так, что каждый меньший диск лежит на большем. Как только все 64 диска будут переложены со стержня, на который Бог Брама сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.
В процессе требуется, чтобы больший диск ни разу не оказывался над меньшим. Монахи в затруднении, в какой же последовательности стоит делать перекладывания? Требуется снабдить их софтом для расчета этой последовательности.

Независимо от Брамы данную головоломку в конце 19 века предложил французский математик Эдуард Люка. В продаваемом варианте обычно использовалось 7-8 дисков (рис. 7).

Рис. 7. Головоломка «Ханойские башни».

Предположим, что существует решение для n-1 диска. Тогда для перекладывания n дисков надо действовать следующим образом:

1) Перекладываем n-1 диск.
2) Перекладываем n-й диск на оставшийся свободным штырь.
3) Перекладываем стопку из n-1 диска, полученную в пункте (1) поверх n-го диска.

Поскольку для случая n = 1 алгоритм перекладывания очевиден, то по индукции с помощью выполнения действий (1) – (3) можем переложить произвольное количество дисков.

Создадим рекурсивную процедуру, печатающую всю последовательность перекладываний для заданного количества дисков. Такая процедура при каждом своем вызове должна печатать информацию об одном перекладывании (из пункта 2 алгоритма). Для перекладываний из пунктов (1) и (3) процедура вызовет сама себя с уменьшенным на единицу количеством дисков.

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

6.3. Синтаксический анализ арифметических выражений

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

Процесс вычисления арифметических выражений можно представить в виде бинарного дерева. Действительно, каждый из арифметических операторов (+, –, *, /) требует двух операндов, которые также будут являться арифметическими выражениями и, соответственно могут рассматриваться как поддеревья. Рис. 8 показывает пример дерева, соответствующего выражению:

Рис. 8. Синтаксическое дерево, соответствующее арифметическому выражению (6).

В таком дереве концевыми узлами всегда будут переменные (здесь x) или числовые константы, а все внутренние узлы будут содержать арифметические операторы. Чтобы выполнить оператор, надо сначала вычислить его операнды. Таким образом, дерево на рисунке следует обходить в концевом порядке. Соответствующая последовательность узлов

называется обратной польской записью арифметического выражения.

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

и операции сложения и вычитания мы будем считывать слева на право, то правильное синтаксическое дерево будет содержать минус вместо плюса (рис. 9а). По сути, это дерево соответствует выражению Облегчить составление дерева можно, если анализировать выражение (8) наоборот, справа налево. В этом случае получается дерево с рис. 9б, эквивалентное дереву 8а, но не требующее замены знаков.

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

Рис. 9. Синтаксические деревья для выражения ab + c при чтении слева направо (а) и справа налево (б).

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

  1. Вычисляющая выражение функция (CalcExpression) находит в строке все знаки «+» и «–», не заключенные в скобки. Эти знаки разбивают выражение на части, содержащие (вне скобок) только операции умножения и деления. Для вычисления значений этих частей вызывается функция CalcMultDiv.
  2. Функция CalcMultDiv находит в строке все знаки «*» и «/», не заключенные в скобки. Эти знаки разбивают выражение на части, содержащие числовые константы, переменную x или выражения в скобках. Для вычисления значений этих частей вызывается функция CalcValuesOrOpenParentheses.
  3. Функция CalcValuesOrOpenParentheses определяет тип попавшего ей на вход выражения. Если это числовая константа или переменная x, то она возвращает их значение. Если это выражение в скобках, то для его вычисления рекурсивно вызывается процедура CalcExpression.

Заметим, что в данном примере вычисления производятся одновременно с анализом строкового выражения. Это приводит к тому, что для некоторых выражений вычисления могут происходить в 100 – 1000 раз медленнее, чем, если бы эти выражения были скомпилированы как часть программы. Если одно и то же выражение требуется вычислить много раз при различных значения переменных, то следует разделить анализ строки и вычисления. Такой подход может позволить ускорить вычисления в сотни раз.

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

6.4. Быстрые сортировки

Простые методы сортировки вроде метода выбора или метода пузырька сортируют массив из n элементов за O(n 2 ) операций. Однако с помощью принципа «разделяй и властвуй» удается построить более быстрые, работающие за O(n log2 n) алгоритмы. Суть этого принципа в том, что решение получается путем рекурсивного разделения задачи на несколько простые подзадачи того же типа до тех пор, пока они не станут элементарными. Приведем в качестве примеров несколько быстрых алгоритмов такого рода.

Алгоритм 1: «Быстрая» сортировка (quicksort).

1. Выбирается опорный элемент (например, первый или случайный).

2. Реорганизуем массив так, чтобы сначала шли элементы меньшие опорного, потом равные ему, затем большие. Для этого достаточно помнить, сколько было найдено меньших (m1) и больших (m2), чем опорный и ставить очередной элемент на место с индексом m1, а очередной больший на место с индексом n-1-m2.

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

3. Если «меньшая» или «большая» часть состоит из одного элемента, то она уже отсортирована и делать ничего не надо. Иначе сортируем эти части с помощью алгоритма быстрой сортировки (то есть, выполняем для нее шаги 1-3).

Как видите, быстрая сортировка состоит из выполнения шагов 1 и 2 и рекурсивного вызова алгоритма для получившихся частей массива.

Алгоритм 2: Сортировка слиянием (merge sort).

  1. Делим массив на две части примерно одинакового размера и, если получившаяся половина массива содержит больше одного элемента, то сортируем ее с помощью сортировки слиянием. Как видите, этот пункт содержит рекурсивное обращение ко всему алгоритму в целом.
  2. Соединяем две отсортированные половины так, чтобы получился один отсортированный массив. Для этого помещаем во вспомогательный массив элементы из первой половины, пока они не превосходят очередного элемента из второй половины. Затем начинаем помещать туда элементы второй половины, пока они не превосходят очередного элемента из первой половины. Затем снова берем элементы первой половины и т.д. Эта операция называется слиянием и требует столько шагов, сколько элементов в обоих соединяемых массивах.

Алгоритм 3: Сортировка деревом (tree sort).

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

Рис. 10. Двоичные деревья поиска, составленные из чисел 1, 3, 4, 6, 7, 8, 10, 13, 14.

Если для каждой вершины высота поддеревьев различается не более чем на единицу, то дерево называется сбалансированным. Сбалансированные деревья поиска также называются АВЛ-деревьями (по первым буквам фамилий изобретателей Г. М. Адельсона-Вельского и Е. М. Ландиса). Как видно на рис. 10а показано сбалансированное дерево, на рис. 10б несбалансированное.

Заметим, что расположение чисел по возрастанию получится, если обходить эти деревья в обратном прядке.

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

Если дерево будет близко к сбалансированному, то сортировка потребует примерно n log2 n операций. Если не повезет и дерево окажется максимально несбалансированным, то сортировка займет n 2 операций.

6.5. Произвольное количество вложенных циклов

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

Для примера напишем процедуру, печатающую все возможные сочетания из k чисел от 1 до n ( ). Числа, входящие в каждое сочетание, будем печатать в порядке возрастания. Сочетания из двух чисел (k=2) печатаются так:

Сочетания из трех чисел (k=3) так:

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

6.6. Задачи на графах

Графом называют графическое изображение, состоящее из вершин (узлов) и соединяющих некоторые пары вершин ребер (рис. 11а).

Более строго: граф – совокупность множества вершин и множества ребер. Множество ребер – подмножество евклидова квадрата множества вершин (то есть ребро соединяет ровно две вершины).

Ребрам можно также присвоить направление. Граф в этом случае называется ориетированным (рис. 11б).

Рис. 11. (а) Граф. (б) Ориентированный граф.

Теория графов находит применения в самых разных областях. Несколько примеров:

  1. Логистика и транспортные системы. Вершинами будут склады с товарами или пункты назначения, а ребра – дороги, их соединяющие.
  2. Маршрутизация сетей. Вершины – компьютеры, соединенные в сеть, ребра – связи между ними. Решается задача о путях передачи данных с одного компьютера на другой.
  3. Компьютерная химия. Модели в виде графов используются для описания путей протекания сложных реакций. Вершины – участвующие в реакциях вещества, ребра – пути превращений веществ. Также графом является изображение структур молекул: вершины – атомы, ребра – химические связи.
  4. Электрические сети.
  5. Сайты в Интернете можно считать узлами ориентированного графа, ребрами которого будут гиперссылки.
  6. И т. д.

Современная теория графов представляет собой мощную формальную систему, имеющую необозримое множество применений.

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

В программировании используются три способа хранения в памяти информации о стуктуре графов.

1) Матрицы смежности

Квадратная матрица M, где как строки, так и столбцы соответствуют вершинам графа. Если вершины с номерами i и j соединены ребром, то Mij = 1, иначе Mij = 0. Для неориентированного графа матрица, очевидно, симметрична. Ориентированный граф задается антисимметричной матрицей. Если ребро выходит из узла i и приходит в узел j, то Mij = 1, а симметричный элемент Mji = -1.

2) Матрица инцидентности

Столбцы матрицы соответствуют вершинам, а строки ребрам. Если ребро с номером i соединяет вершины с номерами j и k, то элементы матрицы Iij = Iik = 1. Остальные элементы i-й строки равны 0.

Просто набор пар номеров вершин, соединенных ребрами.

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

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

Например, классической задачей является поиск пути из одной вершины в другую. Алгоритм поиска должен будет построить дерево возможных путей из начальной вершины, концевыми узлами которого будут вершины, из которых нельзя попасть ни в какую вершину, не принадлежащую ранее построенной ветви (не помеченную как уже посещенную). Задача будет решена, когда один из концевых узлов совпадет с конечной вершиной, путь в которую требуется найти.

6.7. Фракталы

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

Классическим примером является кривая Коха, построение которой показано на рис. 12. Изначально берется отрезок прямой (рис. 12а). Он делится на три части, средняя часть изымается и вместо нее строится угол (рис. 12б), стороны которого равны длине изъятого отрезка (то есть 1/3 от длины исходного отрезка). Такая операция повторяется с каждым из получившихся 4-х отрезков (рис. 12в). И так далее (рис. 12г). Кривая Коха получается после бесконечного числа таких итераций. На практике построение можно прекратить, когда размер деталей окажется меньше разрешения экрана (рис. 12д).

Рис. 12. Процесс построения кривой Коха.

Еще одним примером может служить деревце на рис. 6. Оно также содержит части, подобные всему дереву в целом, что делает его фракталом.

Фракталы, по сути, рекурсивные структуры и их построение естественно производить с помощью рекурсивных процедур.

7. Избавление от рекурсии

Любой рекурсивный алгоритм может быть переписан без использования рекурсии. Заметим, что быстродействие алгоритмов при избавлении от рекурсии, как правило, повышается. Еще одной причиной чтобы избавиться от рекурсии является ограничение на объем хранимых программой локальных переменных и значений параметров одновременно выполняющихся процедур. При очень глубокой рекурсии этот объем возрастает, и программа перестает работать, выдавая ошибку «Stack overflow» (переполнение стека).

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

Ниже представлено несколько вариантов того, как это можно сделать.

7.1. Явное использование стека

Стеком называется структура данных, в которой добавление и извлечение данных происходит с одного конца, называемого вершиной стека (рис. 13). Наглядным образом стека может служить стопка тарелок – добавлять или забрать тарелки можно только сверху. Каждая тарелка соответствует элементу данных.

Рис. 13. Наглядное представление стека. Push (проталкивание) – традиционное название для операции добавления данных в стек, Pop (выталкивание) – традиционное название для операции извлечения данных из стека.

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

При рекурсивных вызовах стек вызовов хранит цепочку из данных об одновременно работающих процедурах. Во всех продвинутых средах разработки эту цепочку вместе с запомненными параметрами процедур можно просмотреть во время отладки. Соответствующая команда обычно называется “Call Stack” (в Delphi ей соответствует сочетание клавиш Ctrl – Alt – S).

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

Для начала реализуем в виде класса стек, хранящий параметры процедуры:

Рассмотрим обобщенную рекурсивную процедуру с двумя вызовами самой себя.

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

Обратите внимание, что рекурсивные вызовы шли сначала для параметров P2, потом для P3. В нерекурсивной процедуре в стек отправляются сначала параметры P3, а только потом P2. Это связано с тем, что при рекурсивных вызовах в стек, по сути, отправляется недовыполненная часть процедуры, которая в нашем случае содержит вызов Recurs(P3).

Упомянутой выше перестановки можно избежать, если вместо стека использовать очередь – структуру данных, где добавление и извлечение элементов происходит с разных концов. Это будет некоторым отступлением от точной имитации процессов при рекурсивных вызовах. Однако в данном примере это кажется более удобным: каждый рекурсивный вызов будет прямо заменяться добавлением параметров в очередь.

7.2. Запоминание последовательности рекурсивных вызовов

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

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

Еще один пример такого запоминания в задаче о вычислении значений многомерных полиномов смотрите тут: http://tvd-home.ru/numerical/polynom.

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

7.3. Определение узла дерева по его номеру

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

Например, пусть требуется выполнить k вложенных циклов по n шагов в каждом:

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

Чтобы избавиться от рекурсии и свести все к одному циклу, обратим внимание, что если нумеровать шаги в системе счисления с основанием n, то каждый шаг имеет номер, состоящий из цифр i1, i2, i3, … или соответствующих значений из массива Indexes. То есть цифры соответствуют значениям счетчиков циклов. Номер шага в обычной десятичной системе счисления:

Всего шагов будет n k . Перебрав их номера в десятичной системе счисления и переведя каждый из них в систему с основанием n, получим значения индексов:

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

Еще один замечательный пример — вычисление по номеру шага перекладываний в задаче о Ханойских башнях смотрите тут: http://algolist.manual.ru/maths/combinat/hanoi.php

Контрольные вопросы

1. Определите, что сделают приведенные ниже рекурсивные процедуры и функции.

(а) Что напечатает приведенная ниже процедура при вызове Rec(4)?

(б) Чему будет равно значение функции Nod(78, 26)?

(в) Что будет напечатано приведенными ниже процедурами при вызове A(1)?

(г) Что напечатает нижеприведенная процедура при вызове BT(0, 1, 3)?

2. Уроборос – змей, пожирающий собственный хвост (рис. 14) в развернутом виде имеет длину L, диаметр около головы D, толщину брюшной стенки d. Определите, сколько хвоста он сможет в себя впихнуть и в сколько слоев после этого будет уложен хвост?

Рис. 14. Развернутый уроборос.

3. Для дерева на рис. 10а укажите последовательности посещения узлов при прямом, обратном и концевом порядке обхода.

4. Изобразите графически дерево, заданное с помощью вложенных скобок: (A(B(C, D), E), F, G).

5. Изобразите графически синтаксическое дерево для следующего арифметического выражения:

Запишите это выражение в обратной польской записи.

6. Для приведенного ниже графа (рис. 15) запишите матрицу смежности и матрицу инцидентности.

Задачи

1. Вычислив факториал достаточно большое количество раз (миллион или больше), сравните эффективность рекурсивного и итерационного алгоритмов. Во сколько раз будет отличаться время выполнения и как это отношение будет зависеть от числа, факториал которого рассчитывается?

2. Напишите рекурсивную функцию, проверяющую правильность расстановки скобок в строке. При правильной расстановке выполняются условия:

(а) количество открывающих и закрывающих скобок равно.
(б) внутри любой пары открывающая – соответствующая закрывающая скобка, скобки расставлены правильно.

Примеры неправильной расстановки: )(, ())(, ())(() и т.п.

3. В строке могут присутствовать скобки как круглые, так и квадратные скобки. Каждой открывающей скобке соответствует закрывающая того же типа (круглой – круглая, квадратной- квадратная). Напишите рекурсивную функцию, проверяющую правильность расстановки скобок в этом случае.

Пример неправильной расстановки: ( [ ) ].

4. Число правильных скобочных структур длины 6 равно 5: ()()(), (())(), ()(()), ((())), (()()).
Напишите рекурсивную программу генерации всех правильных скобочных структур длины 2n.

Указание: Правильная скобочная структура минимальной длины «()». Структуры большей длины получаются из структур меньшей длины, двумя способами:

(а) если меньшую структуру взять в скобки,
(б) если две меньших структуры записать последовательно.

5. Создайте процедуру, печатающую все возможные перестановки для целых чисел от 1 до N.

6. Создайте процедуру, печатающую все подмножества множества <1, 2, …, N>.

7. Создайте процедуру, печатающую все возможные представления натурального числа N в виде суммы других натуральных чисел.

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

Замечание: Данный алгоритм является альтернативой приему накопления суммы. В случае вещественнозначных массивов он, обычно, позволяет получать меньшие погрешности округления.

9. Запрограммируйте быстрые методы сортировки массивов, описанные в разделе 6.4.

10. Создайте процедуру, рисующую кривую Коха (рис. 12).

11. Воспроизведите рис. 16. На рисунке на каждой следующей итерации окружности в 2.5 раза меньше (этот коэффициент можно сделать параметром).

Литература

1. Д. Кнут. Искусство программирования на ЭВМ. т. 1. (раздел 2.3. «Деревья»).
2. Н. Вирт. Алгоритмы и структуры данных.

Илон Маск рекомендует:  Горизонтальный список
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL