Основы программирования — второй семестр 08-09; Михалкович С.С.; III часть

Рекурсия

Определение рекурсии.

Рекурсивные определения. Примеры: n!, a^n. Нерекурсивная часть рекурсивного определения. Праворекурсивное и леворекурсивное определения.

Рекурсия в программировании. Прямая и косвенная рекурсия. Необходимость forward при косвенной рекурсии.

Простые примеры использования рекурсии. Рекурсивное зацикливание.

Понятие рекурсивного спуска и рекурсивного возврата. Графическое изображение рекурсивного спуска и рекурсивного возврата. Глубина рекурсии, текущий уровень рекурсии.

Примеры вычисления n!, a^n.

Сравнение двух способов вычисления a^n по глубине рекурсии и количестве операций.

Пример нахождения минимума в массиве.

Замечания

• О переполнении программного стека
• О накладных расходах на рекурсию
• О замене рекурсии итерацией

Пример вывода списка с помощью рекурсии, применения операции ко всем элементам списка.