Рекурсия и её использование
- Понятие рекурсивного вызова
- Контекст функции
- Ограничение на глубину вложенности
- Принцип: вложенность не должна расти быстрее log(N), где N — количество обрабатываемых данных
- Правильный пример рекурсии: рекуррентно заданная функция
Неправильный пример рекурсии — факториал
- Рекуррентное сведение задачи к задаче меньшей размерности как базис рекурсии
- Пример: вывести все представления числа в виде слагаемых
Домашнее задание
Прочитать о рекурсии в Википедии - Составить программу для вычисления суммы: 2! + 4! + 6! + ... + п!
- Рекурсивную
- Нерекурсивную
Эффективно работающую на относительно больших числах, например, n==10000
- Воспроизвести программу с занятия: ввести число, вывести все представления числа в виде слагаемых
- Решить ту же задачу, но перестановки слагаемых не выводить (например, можно всегда поддерживать упорядоченность слагаемых по возрастанию)
- Заметим, что в варианте с рекурсией некоторые варианты сумм мы считаем многократно (например, сумму из трёх единиц для 6 — трижды, для 3,1,1,1, 2,1,1,1,1 и 1,1,1,1,1. Нет ли более эффективного решения?
Условные обозначения
— тема по Linux - — тема повышенной сложности
- — теоретическое задание
— тема для самостоятельного изучения