9«В» — Рекурсия.

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

1. Используя лишь команды печать(x) при x=0…9, написать рекурсивную программу печати десятичной записи целого неотрицательного числа n.
2. Написать программу подсчета n-того члена последовательности, задаваемого рекуррентной формулой: f(1)=1, f(n) = f([n/2])+f([2n/3]).
3. Написать рекурсивную программу возведения числа в целую неотрицательную степень n с глубиной рекурсии не больше C⋅log₂n.
   (См. также задачу Q здесь.)
4. Написать рекурсивную программу, вычисляющую сумму всех чисел последовательности таким образом: сначала суммируется первая половина последовательности, затем — вторая, затем обе частичные суммы складываются (к подпоследовательностям, конечно же, применяется тот же алгоритм). Числа в последовательности не обязательно целые.
5. Написать программу, реализующую расширенный алгоритм Евклида: по заданным целым числам a, b надо вычислить натуральное d = НОД(a, b) и целые m, n такие, что d = a*m + b*n.
6. Написать рекурсивную программу, которая печатает по одному разу все последовательности длины n, составленные из чисел 1…k (их количество равно k в степени n).
7. Игра «Ханойские башни» состоит в следующем. Есть три стержня. На первый из них надета пирамидка из n колец (большие кольца снизу, меньшие сверху). Требуется переместить кольца на другой стержень. Разрешается перекладывать кольца со стержня на стержень, но класть большее кольцо поверх меньшего нельзя. Составить программу, указывающую требуемые действия.
   (В развитие темы можно также глянуть сюда, задачи S,AS,T,U,V,W,X.)
8. Составить программу, проверяющую сбалансированность квадратных, круглых и фигурных скобок в тексте. (Это [пример) {несбалансированных ]скобок.}
9. Написать программу-калькулятор, вычисляющую значение заданного выражения. В строке ввода допустимы цифры 0…9, точки (отделяют целые части чисел от дробных), круглые скобки, знаки + - * / и пробелы. Программа также должна сообщать о недопустимом выражении (в частности, унарные знаки + или - могут стоять либо в начале выражения, либо после открывающейся скобки). Нельзя пользоваться имеющимися в языке Python средствами разбора и вычисления выражений!
10. Написать рекурсивную программу, которая печатала бы все перестановки чисел 1…n по одному разу.
    (Есть интересные развития темы, например: можно ли сделать так, чтобы соседние перестановки отличались только перестановкой двух соседних чисел?)
11. Написать рекурсивную программу, которая печатала бы все возрастающие последовательности длины k, элементами которых являются натуральные числа от 1 до n. (Предполагается, что k не превосходит n — иначе таких последовательностей не существует.)
12. Ввести натуральное число n. Напечатать все различные представления числа n в виде суммы натуральных чисел. Перестановка слагаемых нового способа не дает.
13. Ввести натуральное число n. Напечатать все различные представления числа n в виде суммы различных натуральных чисел. Перестановка слагаемых нового способа не дает.
14. Ввести натуральное число n. Считая, что введенное число — сумма, подлежащая оплате, напечатать все варианты оплаты этой суммы в банкнотах и монетах, имеющихся в обращении на момент решения задачи. Выделить способ оплаты, требующий минимального числа банкнот.
15. Ввести натуральное число n и напечатать все представления этого числа в виде суммы нескольких квадратов натуральных чисел. Перестановка слагаемых нового представления не дает.
16. Дана полоска из клеток, пронумерованных от 1 до N слева направо. Разрешено снимать или ставить фишку на клетке с номером 1 или на клетке, следующей за самой левой из установленных фишек. Изначально полоска пуста. Нужно разместить фишки во всех клетках.
    Программа должна ввести количество клеток в полоске N (1 ≤ N ≤ 10) и напечатать последовательность номеров клеток, с которыми совершаются действия. Если фишка снимается, то номер клетки должен выводиться со знаком минус. Количество действий не должно превышать 10⁴.
17. В небоскребе N этажей. Известно, что если при падении стеклянного шарика с этажа номер p шарик разбивается, то при падении шарика с этажа номер p+1 он тоже разобьётся. Также известно, что при падении с последнего этажа шарик всегда разбивается.
    Вам надо определить минимальный номер этажа, при падении с которого шарик разбивается. Для проведения экспериментов у вас есть два шарика. Вы можете разбить их все, но в результате вы должны абсолютно точно определить этот номер.
    Программа должна ввести количество этажей в небоскребе N и напечатать наименьшее число бросков, при котором можно всегда решить задачу.
    (См. также задачу Z здесь.)