В предыдущем задании мы рассматривали важный комбинаторный объект: все подмножества множества из \(n\) элементов, что делалось при помощи двоичного представления числа. В этом задании будут генерироваться более сложные комбинаторные объекты, для чего будет использоваться рекурсивная функция. Главная идея такая: пусть нужно построить все двоичные последовательности длины \(n\). Они устроены так: сначала идут все последовательности, начинающиеся с нуля, потом все последовательности, начинающиеся с единицы. В свою очередь все последовательности, начинающиеся с нуля, имеют первым элементом ноль, после которого следует последовательность длины \(n-1\), которые тоже нужно перечислить в лексикографическом порядке.
То есть функцию генерации всех последовательностей длины \(n\) можно реализовать при помощи рекурсивной функции, которая должна вызвать себя два раза: чтобы построить все последовательности длины \(n-1\), предваряя их числом 0, затем чтобы построить все последовательности длины \(n-1\), предваряя их числом 1.
У такой функции должен быть параметр prefix, который обозначает ту часть последовательности,
которая уже построена. Она должна предварять построенную последовательность, то есть должна быть
добавлена к началу построенной последовательности. Функция также имеет параметр \(n\) —
сколько элементов последовательности нужно построить.
Рекурсивный вызов заключается в том, что к префиксу добавляется 0 и вызывается функция для построения последовательности длины \(n-1\), затем к префиксу добавляется 1 и делается такой же вызов.
Окончание рекурсии — когда \(n=0\), в этом случае нужно построить пустую последовательность,
то есть в параметре prefix хранится вся построенная часть и её нужно вывести.