Контрольная работа по теме "Рекурсивные функции"

1. Реализуйте рекурсивную функцию, которая получает строку и возвращает список всех её возможных перестановок.

2. Используйте рекурсию для нахождения НОД двух чисел с помощью алгоритма Евклида.

(Для любых двух натуральных чисел  верно следующее равенство: )

3. Реализуйте рекурсивную функцию, которая принимает число и возвращает все возможные разбиения этого числа на сумму натуральных чисел. Например, для 4 это будет:

4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

4. Дан квадрат n×n, можно двигаться только вправо или вниз. Напишите рекурсивную функцию, которая находит количество возможных путей из левого верхнего угла в правый нижний.
5. Реализуйте функцию, которая считает "двойной факториал" числа:
n!!=n×(n−2)×(n−4)×...×1
6. Реализуйте функцию, которая умножает два числа рекурсивно, используя только сложение