Требования к заданию:

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

1. Написать рекурсивную программу вычисления факториала целого положительного числа. (10)
2. Написать рекурсивную программу вычисления факториала целого неотрицательного числа. (11)
3. Написать рекурсивную программу возведения числа в целую неотрицательную степень. (11)
4. Используя лишь команды печать(x) при x=0…9, написать рекурсивную программу печати десятичной записи целого положительного числа n. (12)
5. Написать программу подсчета n-того члена последовательности, задаваемого рекурентной формулой: f(1)=1, f(n) = f([n/2])+f([2n/3]). (13)
6. Написать рекурсивную программу возведения числа в целую неотрицательную степень n с глубиной рекурсии не больше C⋅log₂ n. (13)
7. Написать программу, которая с помощью алгоритма Евклида считает НОД(a, b). (13)
8. Написать рекурсивную программу, которая печатает по одному разу все последовательности длины n, составленные из чисел 1…k (их количество равно k в степени n). (13)
9. Игра «Ханойские башни» состоит в следующем. Есть три стержня. На первый из них надета пирамидка из n колец (большие кольца снизу, меньшие сверху). Требуется переместить кольца на другой стержень. Разрешается перекладывать кольца со стержня на стержень, но класть большее кольцо поверх меньшего нельзя. Составить программу, указывающую требуемые действия. (14)
10. Составить программу, проверяющую сбалансированность квадратных, круглых и фигурных скобок в тексте. Текст задаётся в файле, myXXX.txt, где XXX — двоичное представление числа вводимого с клавиатуры. (16)
11. Написать рекурсивную программу, которая печатала бы все перестановки чисел 1…n по одному разу. (16)
12. Написать рекурсивную программу, которая печатала бы все возрастающие последовательности длины k, элементами которых являются натуральные числа от 1 до n. (Предполагается, что k не превосходит n — иначе таких последовательностей не существует.) (16)
13. Ввести натуральное число n. Напечатать все различные представления числа n в виде суммы натуральных чисел. Перестановка слагаемых нового способа не дает. (18)
14. Ввести натуральное число n. Напечатать все различные представления числа n в виде суммы различных натуральных чисел. Перестановка слагаемых нового способа не дает. (18)
15. Ввести натуральное число n. Считая, что введенное число — сумма, подлежащая оплате, напечатать все варианты оплаты этой суммы в банкнотах и монетах, имеющихся в обращении на момент решения задачи. Выделить способ оплаты, требующий минимального числа банкнот. (18)
16. Ввести натуральное число n и напечатать все представления этого числа в виде суммы нескольких квадратов натуральных чисел. Перестановка слагаемых нового представления не дает. (18)
17. Написать рекурсивную программу вычисления факториала целого неотрицательного числа находящегося на отрезке [1…1000] (23)