Рекурсия

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

А сейчас предлагаю разобрать задачи, предложенные в этой теме господином Долинским.

Задача Р1 "Сумма М из N"
Основная идея: Идея авторская. Для подсчета количества способов набрать указанную сумму SUM, имея в арсенале последовательность A из N чисел, рассмотрим последний элемент последовательности A[N]. Если последний элемент не превышает указанную сумму, то ответом на задачу можно считать сумму решений меньших подзадач, а именно:
1. Сколькими способами можно набрать сумму SUM-A[N] имея в арсенале последовательность из первых N-1 элементов последовательности A.
2. Сколькими способами можно набрать сумму SUM, имея в арсенале последовательность из первых N-1 элементов последовательности A.
Другими словами: решение общей задачи является сумма решений подзадач, в одной из которых последний элемент последовательности участвует в наборе суммы, а в другой нет. 
Если же последний элемент превышает указанную сумму, то ответом будет только решение меньшей подзадачи 2.
Исходный код: Здесь

Задача Р2 "Разложение числа в сумму"
Основная идея: Авторская идея заключалась в модификации решения предыдущей задачи. Хочу предложить более лаконичное решение. Предлагаю использовать рекурсию с тремя параметрами: 1) предыдущее слагаемое 2) сумма, которую нужно набрать. 2) количество слагаемых в наборе текущей суммы. Принцип того, что в наборе суммы могут участвовать только попарно различные слагаемые будем поддерживать, если условимся что последующее слагаемое в наборе суммы будет строго больше предыдущего (для этого и нужен первый параметр рекурсии). На текущем шаге можно с уверенностью сказать, что последующее слагаемое будет находится в интервале (prev,sum], где prev – это предыдущее слагаемое, а sum – сумма, которую нужно набрать.
Исходный код: Здесь

Задача Р3 "Количество правильных скобочных выражений"
Основная идея: Идея авторского решения мне понравилась. Предлагаю немного другую интерпретацию той же самой идеи. Итак нам известна длина последовательности и два вида скобок: ‘(’ и ‘)’. Предлагаю использоваться рекурсию с тремя параметрами: количество открывающихся и закрывающихся скобок, количество символов до конца последовательности. Последовательно перебираем все позиции последовательности слева направо и делаем вывод: “Какую скобку можно поставить в текущую позицию, чтобы баланс скобок сохранялся на текущем шаге и в дальнейшем?”.
Когда можно ставить открывающуюся скобку:
1.1. Количество открывающихся и закрывающихся скобок равны и есть непройденные позиции.
1.2. Количество оставшихся позиций строго больше разницы между количеством открывающихся и закрывающихся скобок.
Когда можно ставить закрывающуюся скобку:
2.1. Во всех случаях, если количество закрывающихся скобок не превышает количество открывающихся.
Терминальное условие: Все позиции пройдены и количество скобок обоих видов равны.
Исходный код: Здесь

Задача Р4 "Вывод всех разложений"
Основная идея: Вспомним как мы решали задачу “Разложение числа в сумму” и проведем модернизацию решения для того, чтобы помимо количество решений выводились сами решения. В терминальном условии добавится функция вывода получившегося ответа. И для того, чтобы решение получило AC немножко изменим принцип генерации попарно различных слагаемых, а именно: последующее слагаемое будет строго меньше предыдущего. 
Исходный код: Здесь

Задача Р5 "Вывод одного из способов"
Основная идея: Вернемся к решенной задаче “Сумма M из N”. Модифицируем ее таким образом, чтобы теперь мы могли получить не только количество решений, но и хотя бы одно из решений. При этом, найдя первое решение выходим из программы командой exit(0). Рассмотрим интересный прием для получения ответа, предложенным автором. В предыдущей задаче мы использовали следующую конструкцию, назовем ее prevIn-postOut :

1. answer.push_back(i);
2. res += sum_amount(i,curSum-i,itemsAmount+1);
3. answer.pop_back();

Идея проста. До рекурсии элемент кладется в ответ. После рекурсии элемент извлекается из ответа. Такая конструкция очень действенна и наглядна. В данной задаче придется вызывать 3 раза рекурсию, но только для одного вызова нужно применить конструкцию prevIn-postOut для получения ответа. Если бы нужно было вызывать несколько раз такую конструкцию, то следовало поступить, как предлагает Михаил Долинский, а именно завести дополнительный параметр в рекурсии, который показывает добавлен ли предыдущий элемент на предыдущем шаге. При этом, если параметр показывает, что предыдущий элемент был добавлен, то добавляем его в ответ в начале рекурсии, а удаляем в конце:

1. void sum(int localSum, int lastPos,bool isAdd)
2. {
3.   if (isAdd)
4.     answer.push_back(a[lastPos+1]);
5.  
6.     ...
7.  
8.   if (isAdd)
9.     answer.pop_back(); 
10. }

Исходный код (prevIn-postOut):  Здесь
Исходный код(Авторская идея):  Здесь

Задача Р6 "Играем в домино"
Основная идея: Пронумеруем доминошки от 1 до N, где N – количество доминошек. Сгенерируем все перестановки из элементов 1..N. Количество перестановок будет N!. Переберем все перестановки. Ответом к задаче будут первые M элементов одной из перестановок (M<=N), удовлетворяющие условию задачи. При этом M будет максимально. Алгоритм генерации всех перестановок мы разберем в дальнейшем. Сейчас отметим только тот факт, что для получения последующего элемента в текущей перестановке необходимо, чтобы все предыдущие элементы уже стояли на своих местах. Используя этот факт можно не  генерировать перестановки, начинающиеся на доминошки, не образующие правильной последовательности. Это даст существенное отсечение в переборе, если конечно элементы доминошек будут различны.
Исходный код: Здесь
P.S.: В реализации использовал ужасающую конструкцию goto. Если есть предложения как можно обойтись без нее, буду рад услышать. Также использовал новую структуру данных pair<int,int>, которая представляет собой пару элементов. Подробная справку можно почитать здесь

Задача Р7 "Истоки и стоки"
Основная идея: Во входных данных явным образом не указано количество вершин(N), но эту величину легко получить, найдя максимальный индекс города в определении дорог. Зная количество вершин и определение всех дорог можно без труда построить матрицу смежности adj[N][N]. На следующем шаге можно построить матрицу достижимости dest[N][N], при этом элементе dest[i][j] будет равен 1, если из вершины i можно добраться в вершину j, или ноль в противном случае. По умолчанию считаем, что из i-ой вершины всегда можно добраться в i-ую вершину. Для нахождения всех остальных элементов матрицы dest воспользуемся поиском в глубину из фиксированной вершины. Получив матрицу достижимости можно определить ответ к задаче по правилу:
Вершина i является истоком, если i-ая строка матрица достижимости состоит только из true.
Вершина i является стоком, если i-ый столбец матрицы достижимости состоит только из true
Исходный код: Здесь

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

P.S: Этот пост получился очень большим. Он редактировался и добавлялся несколько раз. Думаю его читать и комментировать не очень удобно, поэтому впредь буду использовать правило: одна задача – один пост. Этот пост разбивать не буду, чтобы помнить об  ошибках и не повторять их в дальнейшем.