Анализ рекурсивного алгоритма
Анализ рекурсивного алгоритма — это последовательное раскрытие вызовов функции до базового случая, а затем вычисление результатов снизу вверх. Для надёжного решения важно не угадывать ответ, а явно фиксировать параметры каждого вызова и связи между ними.
Что анализируют в рекурсивной функции
Рекурсивная функция вызывает саму себя с другими аргументами. В условии обычно требуется найти значение функции, число вызовов, глубину рекурсии или результат работы алгоритма. Сначала нужно определить, какие вызовы выполняются фактически: часть ветвей может зависеть от условия и не выполняться вовсе.
Рекурсивная функция — это функция, в теле которой есть вызов этой же функции. В ней обязательно должны быть базовые случаи, для которых ответ известен сразу, и рекурсивные переходы, уменьшающие или изменяющие задачу.
Если на каждом рекурсивном шаге аргумент приближается к базовому случаю, вызовы в конечном итоге завершатся. Если аргумент не изменяется в нужную сторону или базовый случай недостижим, алгоритм может зациклиться.
Перед вычислениями полезно выписать функцию в виде правил: что возвращается при базовом условии и какие значения получают дочерние вызовы в остальных случаях. Например, запись \(F(n)=F(n-1)+F(n-2)\) означает, что один вызов порождает два дочерних вызова.
Дерево вызовов
Дерево рекурсивных вызовов показывает структуру вычисления. Корень — исходный вызов, его дети — непосредственные рекурсивные вызовы, следующий уровень содержит вызовы, возникшие из них. У каждого узла записывают аргумент функции, а после вычисления — результат.
Для вычисления значения дерево читают снизу вверх. Сначала находят ответы в листьях — базовых случаях. Затем подставляют их в родительские узлы. Один и тот же аргумент в разных ветвях является отдельным вызовом, если программа не использует запоминание уже найденных результатов.
Рисуйте дерево слева направо и сразу подписывайте результат у завершённых узлов. Не смешивайте аргумент и значение: F(3) — это вызов, а число после стрелки, например F(3)=5, — его результат.
Пошаговый способ решения
- Запишите исходный вызов функции и все условия.
- Найдите базовый случай: условие, при котором рекурсивного вызова больше нет.
- Для исходного узла выпишите только те дочерние вызовы, которые реально выполняются.
- Продолжайте раскрытие каждого узла до базовых случаев.
- Вычислите листья, затем уровни дерева снизу вверх.
- Проверьте результат обратной подстановкой в формулу функции.
Если функция имеет условный оператор, порядок ветвей также важен. Например, при конструкции «если \(n=0\), вернуть 1, иначе если \(n\) чётно, вернуть \(F(n/2)\), иначе вернуть \(F(n-1)+1\)» для каждого узла сначала проверяют первое условие, затем второе. Нельзя раскрывать обе ветви одновременно.
Что является корнем дерева вызовов для вычисления F(6)?
Разобранный пример
Рассмотрим функцию, заданную псевдокодом: если \(n\le 1\), она возвращает \(1\); иначе возвращает \(F(n-1)+F(n-2)\). Требуется вычислить \(F(5)\). Это типичный пример, где нельзя ограничиться одной цепочкой: каждый нетривиальный вызов порождает две ветви.
Функция F(n) Если n <= 1 то вернуть 1 Иначе вернуть F(n - 1) + F(n - 2) Конец функции
Значение функции равно \(F(5)=8\). Важно: при построении полного дерева вызовов F(3) и F(2) встречаются несколько раз. Если вопрос касается числа вызовов, повторяющиеся узлы нельзя автоматически объединять. Если требуется только значение, одинаковые результаты удобно использовать повторно после проверки.
Что ещё можно получить из дерева
Дерево позволяет определить не только результат функции. Максимальное число рёбер на пути от корня до листа связано с глубиной рекурсии, а порядок, в котором незавершённые вызовы ожидают результаты, объясняет работу стека рекурсивных вызовов. Число узлов показывает количество фактических вызовов, если каждый повторный вызов учитывается отдельно.
| Что ищут | Как определить |
|---|---|
| Значение функции | Вычислить листья и подниматься к корню |
| Глубину рекурсии | Найти самый длинный путь от корня до базового случая |
| Число вызовов | Посчитать все узлы полного дерева, включая повторы |
| Максимальный размер стека | Посчитать одновременно активные вызовы на самом глубоком пути |
Если \(T(n)\) — число вызовов или время работы, структура дерева задаёт рекуррентное соотношение. Например, при двух вызовах \(n-1\) и \(n-2\) число узлов удовлетворяет \(T(n)=T(n-1)+T(n-2)+1\), где единица учитывает текущий вызов.
В задачах на исполнителей и перебор дерево может описывать не вычисления функции, а варианты действий. Тогда важно отличать дерево возможных вариантов от дерева вызовов: в первом узлы обозначают состояния или последовательности команд, а во втором — обращения к функции.
1. Пропуск базового условия и продолжение раскрытия ниже листа. 2. Подмена сложения вызовов их количеством: \(F(a)+F(b)\) — это сумма результатов, а не число ветвей. 3. Объединение одинаковых аргументов при подсчёте вызовов. 4. Раскрытие ветви, которая не выполняется из-за условия. 5. Чтение дерева сверху вниз для вычисления результата: сначала нужны листья. 6. Ошибка в скобках при подстановке результата дочернего вызова.
Как оформить решение на экзамене
Записывайте промежуточные значения компактно: сначала формулу перехода, затем список базовых значений, после этого — вычисления от меньших аргументов к большим. Если требуется число вызовов, составьте отдельную таблицу или выпишите все узлы. Если требуется глубина, отмечайте уровни дерева, начиная с корня на уровне 0.
- Базовый случай найден и применён точно по условию.
- Для каждой ветви раскрыты только реальные вызовы.
- Одинаковые аргументы не объединены при подсчёте узлов.
- Результат проверен обратной подстановкой.
Проверь себя
Главное
- Рекурсивный анализ начинается с базового случая и точной записи перехода.
- Дерево вызовов строят от исходного вызова к листьям, а значения вычисляют снизу вверх.
- При подсчёте вызовов повторяющиеся ветви учитывают отдельно, если нет мемоизации.
- Глубина — длина самого длинного пути, а число вызовов — количество всех узлов.
- Условные ветви раскрывают только тогда, когда их условие действительно выполняется.