Рекурсия

Исходный вариант статьи (В. В. Пупышев, «Рекурсия: плохо или хорошо?») опубликован в журнале «Потенциал».

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

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

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

Представим, что нужно пройти 1000 шагов. Для решения делаем один шаг, остаётся 999: задача упростилась. Сделав такое упрощение 999 раз, дойдём до самой элементарной задачи — шагнуть один раз. Конечно, этот пример слишком прост. Далее мы рассмотрим более сложные примеры, освещающие явление рекурсии как с хорошей так, и с плохой стороны.

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

Числа Фибоначчи

Рассмотрим последовательность чисел $1,1,2,3,5,8,13,21,\dots$ в которой каждое число является суммой двух предыдущих. Это числа Фибоначчи. Формальное их определение таково:

F(1)=1

,

F(2)=1

,

F(n)=F(n-2)+F(n-1)

, если

n>2

.

Функция $F(n)$ задана рекурсивно, то есть «через себя». База — значения функции $F$ на аргументах 1 и 2, а шаг — формула $F(n)=F(n-2)+F(n-1)$ .

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

Проблемы рекурсии и как их решать

При вычислении значения $F(6)$ будут вызваны процедуры вычисления $F(5)$ и $F(4)$ . В свою очередь, для вычисления последних потребуется вычисление двух пар $F(4)$ , $F(3)$ и $F(3)$ , $F(2)$ . Можно нарисовать «дерево рекурсивных вызовов».

Можно заметить, что $F(3)$ вычисляется три раза. Если рассмотреть вычисление $F(n)$ при больших $n$ , то повторных вычислений будет очень много. Это и есть основной недостаток рекурсии — повторные вычисления одних и тех же значений. Кроме того, с рекурсивными функциями связана одна серьезная ошибка: дерево рекурсивных вызовов может оказаться бесконечным и компьютер «зависнет». Важно, чтобы процесс сведения задачи к более простым когда-нибудь заканчивался.

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

Например, рекурсивный алгоритм вычисления чисел Фибоначчи легко дополнить тремя «строчками»:

создать глобальный массив $FD$ , состоящий из нулей;
после вычисления числа Фибоначчи $F(n)$ поместить его значение в $FD[n]$ ;
в начале рекурсивной процедуры сделать проверку на то, что $FD[n]=0$ и, если $FD[n]\neq 0$ , то вернуть $FD[n]$ в качестве результата, а иначе приступить к рекурсивному вычислению $F(n)$ .

Такая рекурсия с запоминанием называется динамическим программированием сверху.

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

$a=b=1$ ;
если $n>2$ , то сделать $n-2$ раз: $c=a+b$ ; $a=b$ ; $b=c$ ;
вернуть ответ $b$ ;

Этот алгоритм линейный по $n$ , то есть для вычисления $n$ -го числа Фибоначчи требуется $n$ шагов. Но здесь есть важная тонкость: число знаков в числе Фибоначчи растёт с $n$ , соответственно, время выполнения операции сложения $c=a+b$ тоже увеличивается. А именно, число знаков в числе Фибоначчи растёт примерно линейно (в любой системе счисления). Это следует из явной формулы:

$F(n)={\frac {1}{\sqrt {5}}}\left(\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right)$ .

Конечно, пока числа не выходят за пределы машинной точности (на компьютерах с 32-битной архитектурой это означает «меньше $2^{32}$ »), сложение выполняется за фиксированое число тактов. Но, начиная с $F(48)$ , уже нельзя использовать элементарные 32-битные целочисленные типы и нужно использовать 64-битные или писать «свою» длинную арифметику, то есть представлять числа в виде массивов цифр в некоторой системе счисления (обычно используют систему с основанием 10000) и писать процедуры сложения таких чисел «столбиком». Например, число десятичных знаков в 1000-м числе Фибоначчи равно 209, и для сложения $F(1001)=F(1000)+F(999)$ «столбиком» в десятичной системе счисления потребуется примерно 209 элементарных операций. Определение сложности задачи вычисления $F(n)$ при больших $n$ довольно трудная задача.

Указанный пошаговый алгоритм вычисления чисел Фибоначчи с учётом затрат на сложения длинных чисел является квадратичным по $n$ (при увеличении $n$ в $k$ раз время вычисления $F(n)$ увеличивается в $k^{2}$ раз), а не линейным как многие считают. Числа Фибоначчи в принципе нельзя подсчитать быстрее, чем за линейное время, так как, чтобы вывести цифры числа Фибоначчи $F(n)$ , уже требуется линейное по $n$ время.

Особенно просто и наглядно функцию вычисления чисел Фибоначчи можно задать на языке Mathematica (см. http://www.wolfram.com):

Простое рекурсивное определение: F(n_) := F(n-1) + F(n-2); F(1) = F(2) = 1;

Рекурсивное определение с запоминанием: F[n_] := (F[n] = F[n-1] + F[n-2]); F[1] = F[2] = 1;

Если определить числа Фибоначчи первым способом, то время вычисления $F[40]$ будет более минуты. Если же использовать второе определение, то 209-значное число $F[1000]$ будет вычислено практически мгновенно, хотя, безусловно, и второй способ далеко не самый оптимальный.

Задача 1

Покажите, что в дереве рекурсивных вызовов рекурсивной функции вычисления числа Фибоначчи $F(n)$ присутствует $F(n-1)$ вызовов $F(2)$ и $F(n-2)$ вызовов $F(1)$ . В частности при вычислении $F(6)$ в дереве присутствуют 5 вызовов $F(2)$ и 3 вызова $F(1)$ .

Задача 2

Покажите, что рекурсивный алгоритм вычисления числа Фибоначчи $F(n)$ требует времени пропорционального $F(n)$ .

Задача 3

Найдите две геометрические прогрессии с различными ненулевыми значениями разности $\lambda$ , удовлетворяющие соотношению $b_{n}=b_{n-1}+b_{n-2}$ . Покажите, что сумма этих прогрессий также удовлетворяет этому соотношению. Представьте $F(n)$ в виде суммы двух геометрических прогрессий, а именно, найдите $C_{1}$ , $C_{2}$ , $\lambda _{1}$ , $\lambda _{2}$ такие, что $F(n)=C_{1}\cdot \lambda _{1}^{n}+C_{2}\cdot \lambda _{2}^{n}$ .

Задача 4

Напишите рекурсивную процедуру вычисления чисел Фибоначчи, основанную на рекуррентных формулах: $F(2n)=2F(n+1)F(n)-F(n)^{2}$ и $F(2n+1)=F(n+1)F(n)+2F(n)^{2}+(-1)^{n}$ . Убедитесь в правильности этих формул с помощью численного эксперимента. Нарисуйте дерево рекурсивных вызовов для $n=2^{10}=1024$ и $n=2^{10}-1=1023$ . Как растёт размер этого дерева в зависимости от $n$ ? Выведите формулы зависимостей $F(2n)$ и $F(2n+1)$ от $F(n)$ и $F(n-1)$ . Напишите рекурсивную функцию, использующую эти четыре формулы в зависимости от чётности $n$ так, чтобы в дереве рекурсивных вызовов были только такие $F(m)$ , для которых двоичная запись $m$ есть левая часть двоичной записи числа $n$ , дополненая справа нулём или единицей.

Задача о золотой горе

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

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

Каждый шаг может идти диагонально вниз направо или диагонально вниз налево.
Количество строк в треугольнике $>1$ , но $<100$ .
Числа в треугольнике все целые от 0 до 99 включительно.

В примере, описанном выше, это путь 7, 3, 8, 7, 5, дающий максимальную сумму 30.

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

Выходные данные: Наибольшая сумма, записанная как целое число в файл OUTPUT.TXT. Для нашего примера это будет число 30.

В примере, описанном выше, это путь 7, 3, 8, 7, 5, дающий максимальную сумму 30.

Пример входных данных:

Эту задачу можно встретить и под названием «Золотая гора» — нужно спуститься с горы и собрать как можно больше золота.

Можно заметить, что в любом месте горы начинается гора меньшего размера, будем называть такие горы горками. Пусть число $a(i,j)$ есть число в треугольнике, находящееся в $i$ -й строчке на $j$ -м месте, а число $(i,j)$ есть максимальное значение суммы, которое можно получить спускаясь с горки, начиная с этого элемента. Понятно, что $(i,j)$ есть число $a(i,j)$ плюс максимум из двух вариантов: $(i+1,j)$ и $(i+1,j+1)$ . Эти два варианта соответствуют тому, что мы можем спуститься вниз-вправо или вниз-влево. Получилось рекурсивное определение: $S(i,j)=a(i,j)+\max {\Big (}S(i+1,j),\;S(i+1,j+1){\Big )}$ . На основе этой рекуррентной формулы можно написать рекурсивный алгоритм. Но нужно быть осторожным. Попробуем вычислить время работы нашего алгоритма при входных данных максимального размера — 100 строк. Рекурсивный алгоритм вычисления функции $S(i,j)$ перебирает все возможные пути. Сколько их? На каждом шаге есть возможность выбрать один вариант из двух (направо или налево). Количество шагов равно количеству строк треугольника. Значит, количество всех путей равно $2^{100}$ (Покажите, что число путей из вершины до $j$ -го элемента $i$ -й строчки равно биномиальному коэффициенту $C_{i}^{j}$ ) Это очень большое число. Столько вариантов не успеет перебрать даже самая мощная вычислительная техника. Если предположить, что машина просматривает миллиард вариантов в секунду, то понадобится ${\frac {2^{100}}{10^{9}}}$ секунд. Чтобы считать было удобнее, заметим, что ${\frac {2^{100}}{10^{9}}}={\frac {16^{25}}{10^{9}}}>10^{25}/10^{9}=10^{16}$ секунд, что соответствует более, чем $10^{12}$ часов, или более $10\,000\,000$ лет. Понятно, что такая программа никому не нужна, её результаты узнать невозможно. За такое время все компьютеры, решающие эту задачу, превратятся в пыль.

На рисунке обозначены две горки (треугольники): одна с вершиной в числе 3, другая с вершиной в числе 8. Эти горки пересекаются, и их пересечение тоже горка с вершиной в числе 1. Можно заметить, что при вычислении самого лучшего пути по рекурсивному алгоритму горка с вершиной в числе 1 будет использоваться дважды. Для горок с вершинами в нижних строчках повторных вызовов будет ещё больше. Это и есть причина медленности работы алгоритма.

Решить эту задачу за разумное время помогает динамическое программирование. Суть динамического программирования хорошо описана в книге Р. Беллмана ^[1]. Есть и более современные учебники ^[2], ^[3], в них можно найти много интересных алгоритмов, основанных на динамическом программировании.

Общая идея динамического программирования заключается в том, что мы рассматриваем вместо одной задачи целое семейство задач. Это семейство задач у нас будет таким: найти наилучший путь из вершины $(i,j)$ . Для каждой пары $i,j$ получим одну задачу. При $i=1$ и $j=1$ получается исходная задача, которую нам нужно решить. Начнём решать эти задачи с простых: сначала для нижней строчки, затем второй снизу и так далее, пока не дойдём до самой верхней строчки треугольника.

По сути, идея динамического программирования заключается в запоминании вычисленных значений $(i,j)$ . Их можно рассматривать как двумерный массив, элементы которого пошагово вычисляются с последней строчки, снизу — вверх.

Подсчитаем количество шагов алгоритма, основанного на динамике. Если количество строк $N$ , то длины строк представляют собой последовательные натуральные числа $1,2,\dots ,N$ . Элемент массива вычисляется один раз за небольшое фиксированное количество элементарных операций по формуле $(i,j)=a(i,j)+\max {\Big (}S(i+1,j),\;S(i+1,j+1){\Big )}$ . Значит время работы всего алгоритма пропорционально количеству элементов в нашем треугольнике (а в общем случае — количеству задач в семействе). Ответ равен $1+2+3+\dots +N={\frac {N(N-1)}{2}}=\Theta (N^{2})$ . Символ $\Theta (N^{2})$ означает «примерно пропорционально $N^{2}$ ». Действительно, если мы ${\frac {N(N-1)}{2}}={\frac {N^{2}-N}{2}}$ разделим на $N^{2}$ , то получим ${\frac {1-1/N}{2}}$ , что очень близко к константе ${\frac {1}{2}}$ (чем больше $N$ , тем ближе).

Задача 5

Пусть значения чисел $a(i,j)$ в треугольнике не хранятся в массиве, а быстро вычисляются некоторой внешней функцией от двух аргументов. Придумайте алгоритм, который использует память $\Theta (N)$ и работает время $\Theta (N^{2})$ .

Подсказка: В памяти достаточно хранить значения $(i,j)$ для одной последней строчки — самой верхней из рассмотренных.

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

Задача «Сделай палиндром»

Палиндром — это последовательность символов, которая слева-направо и справа-налево пишется одинаково. Например «АБА» или «АББ ББА». Дана последовательность символов. Какое минимальное количество символов нужно удалить из неё, чтобы получить палиндром?

Длина последовательности не больше 20 символов. Ограничение на время работы программы: 5 секунд.

Пример: Вход: ТИТ ЕЛЕ ЛЕТИТ. Выход: 2

Эта задача давалась на районной олимпиаде школьников Удмуртской республики в 1998 году. Рассмотрим её решение, основанное на рекурсии.

Если строка имеет вид ${h\;\alpha \;t}$ , где $h$ и $t$ символы, а $\alpha$ — подстрока, возможно пустая. Пусть $S(x)$ — вычисляет минимальное количество символов, которые нужно убрать из строки $x$ , чтобы оставшаяся строка была палиндромом.

Базой рекурсии являются строки из одного символа и пустая строка — все они палиндромы по определению, и для них $S=0$ . Шаг рекурсии состоит из двух частей:

$S(h\;\alpha \;t)={\begin{cases}S(\alpha ),&h=t;\\\min {\Big (}S(\alpha \,t)+1,\;S(h\,\alpha )+1,\;S(\alpha )+2{\Big )},&h\neq t.\end{cases}}$

Получается, что функция $S$ иногда три раза вызывает себя для меньших строк, чтобы затем из результатов выбрать минимальный. Легко заметить, что тут много повторных вычислений. Избавиться от них поможет запоминание значений $S$ при различных $x$ , которые встречались при вычислении. Однако, тут есть одна техническая проблема. Заметим, что $x$ — это строка. Получается, нужно быстро запоминать и находить значения по заданной строке. Эту задачу решают хэш-таблицы. Но в данном случае можно обойтись и без них. Ясно, что в качестве $x$ могут выступать лишь подстроки исходной строки, то есть некоторые кусочки подряд идущих символов из исходной строки. Каждая подстрока определяется двумя числами — номером первого символа и номером последнего.

Соответственно, получается двупараметрическое семейство задач. Задача $P(i,j)$ , где $j>i$ , есть поиск решения для строки, составленной из символов исходной строки с $i$ -го по $j$ -й символ включительно. Ответы на эти задачи естественно хранить в обычном двумерном массиве. Задачи $P(i,i)$ и $P(i,i+1)$ имеют очевидное решение $S=0$ . То есть «диагональ массива» и следующая сверху «диагональ» заполнены нулями. На следующем шаге можно решить задачи вида $P(i,i+2)$ , затем $P(i,i+3)$ и так далее. В конце концов мы доберёмся до задачи $P(1,n)$ , соответствующей исходной задаче ( $n$ — длина данного слова).

Алгоритм Евклида

Даны два натуральных числа. Найти самое большое натуральное число, которое делит оба без остатка. Такое число называется наибольший общий делитель (НОД) (GCD — Greatest Common Divisor).

Пример: Вход: 18, 600 Выход: 6

Есть очень простой алгоритм: давайте перебирать все числа от минимального из заданных до 1 и проверять, делит ли очередное число оба заданных. Первое такое число и будет НОД. У этого алгоритма есть существенный недостаток — маленькая скорость работы. Например для чисел $1\,000\,000\,001$ и $1\,000\,000\,000$ придётся выполнить $1\,000\,000\,000$ проверок. Более эффективно эту задачу решает алгоритм Евклида, основанный на двух простых свойствах $\operatorname {GCD} (a,b)$ :

$GCD(a,Ka)=a$ , где $K$ — натуральное число;
Если $a<b$ , то $GCD(a,b)=GCD(a,b-a)$ .

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

Если после вычитания $b-a$ получается число, большее $a$ , операцию вычитания можно повторить. Так можно продолжать, пока разность не станет меньше $a$ . Можно догадаться, что вместо нескольких вычитаний достаточно выполнить одну операцию деления с остатком и взять получившийся остаток. Запишем формулы, которые позволят нам определить рекурсивную функцию вычисления НОД:

$GCD(a,b)={\begin{cases}a,&b=Ka,\\b,&a=Kb,\\GCD(a,\;b\ \operatorname {mod} \ a),&b\geqslant a;\\GCD(a\ \operatorname {mod} \ b,\;b),&a\geqslant b.\end{cases}}$

Запись « $a\ \operatorname {mod} \ b$ » означает «остаток при делении $a$ на $b$ ». Здесь $K$ — натуральное число.

Оценить количество шагов данного алгоритма достаточно сложно, но скорость его очень велика. Хватит 50 шагов этого алгоритма, чтобы найти НОД любой пары чисел, каждое из которых не превышает $2\,000\,000\,000$ . Интересно отметить, что дольше всего алгоритм работает тогда, когда данные числа есть пара соседних чисел Фибоначчи. Число шагов в алгоритме Евклида напрямую связано с длиной разложения рационального числа ${\frac {a}{b}}$ в цепную дробь. Разложением положительного числа $x$ в цепную дробь называется представление $x=a_{0}+a_{1}/(a_{2}+1/(a_{3}+1/(a_{4}+\dots )))$ , где числа $a_{i}$ натуральные. Разложение дробей (рациональных чисел) в цепную дробь конечно. Вот примеры разложений отношений соседних чисел Фибоначчи в цепную дробь:

${\frac {3}{5}}={\frac {1}{\displaystyle 1+{\frac {1}{\displaystyle 1+{\frac {1}{2}}}}}}$ , ${\frac {5}{8}}={\frac {1}{\displaystyle 1+{\displaystyle {\frac {1}{\displaystyle 1+{\frac {1}{\displaystyle 1+{\frac {1}{2}}}}}}}}}$ , ${\frac {8}{13}}={\frac {1}{\displaystyle 1+{\displaystyle {\frac {1}{\displaystyle 1+{\frac {1}{\displaystyle 1+{\frac {1}{\displaystyle 1+{\frac {1}{2}}}}}}}}}}}$ .

Задача 6

Докажите, что разложение в цепную дробь эквивалентно алгоритму Евклида. Докажите, что $\operatorname {GCD} (F(n+1),\;F(n))=1$ и число шагов в алгоритме Евклида для пары ${\Big (}F(n+1),\;F(n){\Big )}$ равно $n$ . Верно ли, что $F(50)>2\,000\,000\,000$ ?

Задача 7

Докажите, что на парах вида ${\Big (}k,\;F(n+1){\Big )}$ , $k=1,2,\dots ,F(n+1)-1$ алгоритм Евклида дольше всего работает при $k=F(n)$ , и число шагов алгоритма при этом равно $n$ .

При построении рекурсивной функции важно ответить на следующие вопросы:

Что будет базой рекурсии?
Что будет шагом рекурсии?
Почему выполнение шагов рекурсии всегда приведёт к базе?
Какова будет глубина рекурсии при данном значении аргументов? Глубина рекурсии — это глубина дерева рекурсивных вызовов, то есть длина максимального пути по стрелочкам из вершины до одного из элементарных (базовых) значений функции.
Как растёт размер дерева рекурсивных вызовов при увеличении входных данных? Будут ли повторяющиеся вызовы в этом дереве и имеет ли смысл делать рекурсию с запоминанием?

Одно из важных достоинств рекурсивных алгоритмов заключается в том, что они просты и наглядны. Но рекурсия не всегда является эффективным (самым быстрым) решением. Рекурсия использует мало памяти, но работать может довольно долго, как в примере с числами Фибоначчи.

Задача 8

Есть несколько алгоритмов Евклида, основанных на различных рекуррентных соотношениях для НОД:

$\operatorname {GCD} (a,b)=\operatorname {GCD} (b,a\ \operatorname {mod} \ b)$ ;
$\operatorname {GCD} (a,b)=\operatorname {GCD} (b,\min(|a\ \operatorname {mod} \ b|,\;b-|a\ \operatorname {mod} \ b|);$
$\operatorname {GCD} (a,b)={\begin{cases}\operatorname {GCD} \left(a,\;{\frac {b}{2^{k}}}\right),&a{\mbox{ is odd, and }}b=b'\cdot 2^{k},\\2^{k}\cdot \operatorname {GCD} \left({\frac {a}{2^{k}}},\;{\frac {b}{2^{k}}}\right),&a{\mbox{ and }}b{\mbox{ are even, and }}a=a'\cdot 2^{k},\;b=b'\cdot 2^{k},\\\operatorname {GCD} (b,\;a-b),&a{\mbox{ and }}b{\mbox{ are odd, and }}a>b.\end{cases}}$

Эффективность этих алгоритмов можно оценивать с помощью среднего числа шагов алгоритма, необходимых для вычисления $\operatorname {GCD} (m,N)$ , где $N$ фиксированно, а $m$ пробегает значения $1,2,\dots ,N-1$ . Известно, что это число примерно пропорционально $\log _{2}N$ . Вычислите экспериментально коэффициенты пропорциональности для указанных трёх случаев. Явные выражения для этих коэффициентов довольно сложны.

Задачи для самостоятельного решения

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

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

Задача 9

Напишите две рекурсивные процедуры вычисления $f(a,n)=a^{n}$ , основанные на двух различных соотношениях:

$f(a,n)=a\cdot f(a,n-1)$
$f(a,n)={\begin{cases}f^{2}(a,n/2),&{\mbox{ if }}n{\mbox{ is even,}}\\a\cdot f(a,n-1),&{\mbox{ if }}n{\mbox{ is odd.}}\end{cases}}$

База рекурсии в обоих случаях $f(a,0)=a^{0}=1$ . Какое получается дерево рекурсивных вызовов при $n=1000$ ? Имеет ли смысл запоминать вычисленные значения? Чему равно число шагов при $n=1000$ ? Какая из процедур оказалась более эффективной? Покажите, что в случае (2) число рекурсивных вызовов (число вершин в дереве рекурсивных вызовов) ограничено сверху числом $2(\log _{2}n+1)$ .

Задача 10

Найдите число различных путей из точки $A$ в точку $B$ по стрелочкам. Напишите программу, которая вычисляет число этих путей для таких треугольных конфигураций (графов) со стороной $n$ .

Задача 11

Число правильных скобочных структур длины 6 равно 5: ()()(), (())(), ()(()), ((())), (()()).

Напишите рекурсивную программу генерации всех правильных скобочных структур длины $2n$ . Определение правильной скобочной структуры можно задать в нотации EBNF (в расширенной форме Бэкуса — Наура) рекурсивно:

s ::= '(' s ')' | s s | ''

Эта строчка содержит рекурсивное определение объекта s: «объект типа s может быть получен из объекта типа s с помощью окружения его открывающейся и закрывающейся круглой скобки, или с помощью приписывания двух объектов типа s друг к другу, либо это просто пустое слово». Вертикальная черта в нотации EBNF означает союз «или». С помощью одинарных кавычек выделяют символы или строки символов, пробелы играют роль разделителей.

Задача 12

Чему равно число $c_{n}$ правильных скобочных структур длины $2n$ ? Найдите рекуррентную формулу для числа $c_{n}$ , а именно выразите $c_{n}$ через все предыдущие $c_{n-1},\dots ,c_{1}$ . Напишите программу, которая вычисляет число $c_{n}$ правильных скобочных структур длины $2n$ .

Подсказка: найдите перебором первые элементы последовательности $c_{n}=\{1,2,5,\dots \}$ . Рассмотрите соотношения соседних элементов и догадайтесь до явной формулы.

Второй способ. Задача решается методом динамического программирования. Число различных путей из $A$ в $B$ по стрелкам на рисунке из задачи 10 равно числу правильных скобочных структур длины 6 (стрелка вверх соответствует открывающей скобке, а стрелка вниз — закрывающей). Придумайте способ последовательного вычисления числа различных путей из вершины $A$ до различных вершин графа. Сколько памяти использует ваша программа для вычисления $c_{n}$ в зависимости от $n$ ?

Задача 13

Известный алгоритм быстрой сортировки Хоара также основан на рекурсии. Пусть нам нужно отсортировать кусочек массива $A$ от элемента с индексом $b$ по элемент с индексом $e$ включительно. Перераспределим элементы на этом кусочке так, чтобы вначале стояли элементы меньшие либо равные $A_{b}$ , а потом элементы большие либо равные $A_{b}$ . Пусть последний элемент в первом кусочке оказался на месте $c$ . Вызовем рекурсивно сортировку двух кусочков от $b$ до $c$ и от $c+1$ до $e$ включительно, (если, конечно, эти кусочки состоят более, чем из одного элемента). Воплотите эту идею в работающую процедуру сортировки массива. Проведите эксперименты по оценке средней глубины дерева рекурсии и времени работы алгоритма в зависимости от размера массива. Рассмотрите случаи а) случайного массива, б) массива, упорядоченного по возрастанию, и в) массива, упорядоченного по убыванию.

Задача коммивояжёра

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

Коммивояжёр (франц. commis voyageur), разъездной представитель торговой фирмы, предлагающий покупателям товары по имеющимся у него образцам, каталогам и тому подобное.

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

Задача коммивояжёра — побывать во всех городах (не менее одного раза) и при этом потратить как можно меньше денег на проезд и вернуться обратно.

Формулировка задачи

внутри города проезд ничего не стоит;
проезд между двумя городами напрямую стоит одинаково в оба конца;
стоимость — целое число от 1 до 10000;
городов не более 100.

Стоимости проезда между парами городов записаны в следующем формате:

<Количество стоимостей> <Начальный город>
<Город> <Город> <Стоимость>
<Город> <Город> <Стоимость>
<Город> <Город> <Стоимость>
…

Результат записывается в следующем формате:

<Количество городов в пути>
<Город> <Город> <Город> …

Город задаётся названием без пробела. Длина названия города не более 30 символов. Программа должна реагировать на клавишу ESC. Если ESC была нажата, то в течении 10 секунд программа должна записать результат и закончить работу.

Кажется, что для решения такой задачи достаточно хранить самые оптимальные промежуточные пути и вот он динамический алгоритм. Например, рассмотрим тройки городов и для каждой тройки определим в какой последовательности лучше всего её проходить. Затем рассмотрим все четвёрки городов. Решения для четвёрок можно найти на основе известных решений для троек и так далее. Но дело в том, что число возможных наборов $k$ городов и $n$ возможных очень быстро растёт с $n$ и $k$ . Например, 50 городов из 100 можно выбрать 100 891 344 545 564 193 334 812 497 256 способами. Таким образом, запоминать промежуточные решения нет никакой возможности — их слишком много даже для $n=100$ , а на практике нужно решать задачи с $n=10^{6}$ . Для задачи коммивояжёра на плоскости можно использовать ряд эвристических идей, которые позволяют находить приемлемые решения за разумное время. Но при этом даже для случая точек на плоскости задача коммивояжёра остаётся полиномиально неразрешимой, то есть не существует алгоритма, который бы находил самый оптимальный путь коммивояжёра за время ограниченное полиномом $C+n^{k}$ произвольной степени $k$ при любой константе $C$ .

Снежинка Коха

Снежинка Коха — это фрактальное множество точек на плоскости, которое похоже на снежинку.

Здесь приведена программа на языке PostScript. Этот код интерпрерируется программой GSView, которую можно взять на сайте http://www.ghostscript.com.

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

В математике, в отличие от программирования, допускаются такие бесконечные рекурсивные определения. На каждом шаге у нас получается некоторая обычная фигура (не фрактал), а в пределе (после бесконечного числа шагов) получается фрактал. Если положить, что длина стороны исходного треугольника равна 1, то длина стороны шестиугольной звезды равна ${\frac {1}{3}}$ . Длина стороны следующей фигуры ещё в три раза меньше, то есть ${\frac {1}{9}}$ . Можно записать общую формулу: $l_{n}={\frac {1}{3\cdot 3\cdots 3}}={\frac {1}{3^{n}}}$ . Заметьте, что число сторон $m_{n}$ растёт от номера шага как $3,12,48,\dots$ , то есть $m_{n}=3\cdot 4^{n}$ . Периметр $P_{n}$ фигуры, получающейся на шаге $n$ , есть произведение числа сторон на длину: $P_{n}=l_{n}\cdot m_{n}=3\cdot {\frac {4^{n}}{3^{n}}}=3\left({\frac {4}{3}}\right)^{n}$ . Таким образом, периметр фигуры растёт с каждым шагом и стремится к бесконечности.

Задача. Пусть две вершины начального правильного треугольника лежат в точках $(0;0)$ и $(1;0)$ . Какие ещё есть точки с рациональными координатами, принадлежащие снежинке Коха?

Программа «Снежинка Коха»

%!PS-Adobe
 /inch {72 mul} def
 /depth 6 def       % глубина рекурсии
 /baseX 1 inch def  % положение левого нижнего
 /baseY 5 inch def  % угла исходного треугольника
 /edge  6 inch def  % длина стороны треугольника
 0.8 setlinewidth   % толщина линии
 % buildElem - ГЛАВНАЯ РЕКУРСИВНАЯ ФУНКЦИЯ
 /buildElem {
   2 copy
   /recDepth 0 def
   /L 0 def
   /L exch store        % L        = arg2
   /recDepth exch store % recDepth = arg1
   recDepth 0 le {
     newpath 0 0 moveto L 0 rlineto stroke
   } {
     gsave
       /recDepth recDepth 1 sub store
       /delta L 3 div def
       recDepth delta buildElem
       gsave
         dup 0 translate 60 rotate
         buildElem
         dup 0 translate -120 rotate
         buildElem
       grestore
       dup 2 mul 0 translate
       buildElem
       pop pop
     grestore
   } ifelse
 } def
 gsave
   baseX baseY translate 60 rotate
   depth edge buildElem
   edge 0 translate -120 rotate
   buildElem
   edge 0 translate -120 rotate
   buildElem
   pop pop
 grestore
 stroke
 showpage

Заключение

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

Дальнейшее чтение

↑ Беллман Р. Динамическое программирование. — М.: Изд-во иностр. лит., 1960.
↑ Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир 1979.
↑ Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 1999.

[1] Беллман Р. Динамическое программирование. — М.: Изд-во иностр. лит., 1960.

[2] Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир 1979.

[3] Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 1999.

[1]

[2]

[3]