Рекурсивный алгоритм
Рекурсивный алгоритм — это алгоритм, который в процессе выполнения обращается к самому себе, но уже для решения задачи меньшего размера. Такой подход позволяет описывать сложные задачи через более простые однотипные задачи.
Рекурсивный алгоритм состоит из двух частей. Базовый случай задаёт непосредственный ответ для самой простой задачи. Рекурсивный шаг сводит исходную задачу к задаче меньшего размера и вызывает тот же алгоритм. Если базового случая нет или размер задачи не уменьшается, выполнение может продолжаться бесконечно.
В этой схеме \(F(n)\) обозначает результат для задачи размера \(n\), а \(F_0\) — ответ в базовом случае. При выполнении образуется последовательность вызовов; её можно представить как дерево рекурсивных вызовов. Число последовательных вызовов связано с глубиной рекурсии.
Факториал определяется так: \(0!=1\), а \(n!=n\cdot(n-1)!\) при \(n>0\). Поэтому для вычисления \(4!\) алгоритм вызывает себя для \(3\), затем для \(2\), \(1\) и \(0\): \(4!=4\cdot3\cdot2\cdot1\cdot1=24\). Вызов для \(0\) является базовым и останавливает рекурсию.
Рекурсивный алгоритм и цикл могут решать одну и ту же задачу, но работают по-разному. Рекурсия создаёт новые вызовы самого алгоритма, а цикл повторяет команды внутри одного выполнения. Рекурсию часто можно заменить итерацией, однако расход памяти и удобство описания могут отличаться.
Что обязательно должно быть в корректном рекурсивном алгоритме?
Главное
- Рекурсивный алгоритм обращается к самому себе для задачи меньшего размера.
- В нём должны быть базовый случай и рекурсивный шаг.
- Если задача не уменьшается, рекурсия может стать бесконечной.