Понятие рекурсии
Рекурсия – определение некоторого понятия через само себя.
Фракталы – самоподобные множества нецелой размерности.
Рекурсивный алгоритм – алгоритм, определяемый через себя (факториал, числа Фибоначчи).
Явная рекурсия: A → A → …
Неявная рекурсия: A → B → A → …
Рекурсивные данные – структура данных, определяемая через себя (бинарные деревья, списки).
Рекурсивные алгоритмы:
- база рекурсии - условие выхода
- шаг рекурсии - операторы с вызовом
Реализация механизма рекурсии
Локальные данные подпрограммы хранятся в сегменте стека. Дисциплина отработки рекурсивных вызовов остаётся та же, т.е. все локальные данные тоже помещаются в стек (данные предварительного вызова остаются в сегменте стека). Этот процесс называется прямым ходом рекурсии.
Прямой ход рекурсии продолжается до исчерпания сегмента стека (программа аварийно завершается) или до достижения базы рекурсии, после чего запускается процесс обратного хода рекурсии (серия завершений вызовов подпрограммы). При этом из стека вынимаются сохранённые ранее значения и используются для последующих вычислений.
| Рекурсия | Итерация |
|---|---|
| от сложного к простому | от простого к сложному |
| описание сложного через такие же простые | построение сложного из более простых |
| компактна, красива, понятна | некомпактна, некрасива |
| накладные расходы (память, лишние вызовы) |
без накладных расходов |