Теория:
В процессе разработки алгоритмов для решения сложных задач часто возникает потребность в использовании одной и той же последовательности действий в различных частях одного алгоритма. Такую последовательность действий удобно оформлять отдельным алгоритмом, который вызывают в нужных местах основного алгоритма.
Вспомогательный алгоритм — это самостоятельный, логически завершённый алгоритм, предназначенный для решения определённой подзадачи в рамках более сложной общей задачи.
Команда выполнения вспомогательного алгоритма называется вызовом и записывается в теле основного алгоритма.
Пример \(1\)
Робот расположен в верхнем левом углу игрового поля. Необходимо составить алгоритм, после которого Робот нарисует узор, представленный на рисунке. Конечное положение Робота может быть любым.
Заметим, что в узоре четыре раза повторяется один и тот же элемент:
Разработаем вспомогательный алгоритм для изображения этой фигуры.
Теперь для получения необходимого нам узора достаточно будет вызвать по имени наш вспомогательный алгоритм.
Пример \(2\)
Создадим вспомогательный алгоритм «Многоугольник» для исполнителя Черепаха с параметрами \(k\) — количество углов, \(n\) — длина стороны правильного многоугольника.
При обращении к вспомогательному алгоритму \(k\) и \(n\) будут теми величинами, для которых он будет исполнен.
Основной алгоритм с вызовом вспомогательного алгоритма «Многоугольник» может выглядеть так:
Рекурсивный алгоритм — алгоритм, в котором прямо или косвенно содержится ссылка на него же, как на вспомогательный алгоритм.
Пример \(3\)
Возведение числа в степень
Задача: вычислить \(A\) в степени \(N\) (), где \(A\) — число, а \(N\) — целая неотрицательная степень.
Рекурсивный алгоритм
1. Если \(N = 0\).
Ответ: \(1\) (любое число в степени \(0\) равно \(1\)) — базовый случай.
2. Иначе (если \(N > 0\)).
Ответ: \(A~*\) — рекурсивный вызов.
Как это работает?
- Возвести \(2\) в степень \(3\) \(: 2~*\) Возвести в степень \((2, 2)\).
- Возвести в степень \((2, 2) : 2~*\) Возвести в степень \((2, 1)\).
- Возвести в степень \((2, 1) : 2 ~*\) Возвести в степень \((2, 0)\).
- Возвести в степень \((2, 0) : 1\) (базовый случай).
Теперь подставляем результаты обратно:
- Возвести в степень \((2, 1) = 2 * 1 = 2\).
- Возвести в степень \((2, 2) = 2 * 2 = 4\).
- Возвести \(2\) в степень \(3 = 2 * 4 = 8\).