Рекурсивной называется процедура, в которой имеется обращение к самой к себе.
Не все исполнители могут использовать рекурсии. Такая возможность имеется в «Стрелочка». При программировании некоторых задач рекурсия может служить альтернативой циклу.
Пример: начальное положение «Стрелочка» - произвольная точка в первой строке рабочего поля, направление «вправо». Требуется построить линию, идущую из этой точки до правой границы области.
Сначала приведем на языке «Стрелочки» программу, в которой используется цикл.
Алгоритм Путь 1
Дано: исполнитель в точке А
Надо: воспроизвести образец
нач
пока впереди не стена
нц
шаг
кц
кон
А теперь воспользуемся рекурсией, для чего опишем процедуру ЛИНИЯ_1
Алгоритм Путь 1_1
Дано: исполнитель в точке А
Надо: воспроизвести образец
нач
делай ЛИНИЯ_1
кон
процедура ЛИНИЯ_1
шаг
делай ЛИНИЯ_1
конец процедуры
В теле этой процедуры присутствует команда обращения к самой себе: делай Линия_1.
Пошаговое исполнение (трассировка) такой программы:
В информатике , рекурсия является методом решения проблемы , когда решение зависит от решения небольших экземпляров одной и той же задачи. Такие проблемы, как правило, можно решить итерацией , но для этого необходимо идентифицировать и индексировать более мелкие экземпляры во время программирования. Рекурсия решает такие рекурсивные проблемы с помощью функций, которые вызывают сами себя из собственного кода. Этот подход может применяться ко многим типам задач, и рекурсия является одной из центральных идей информатики. Сила рекурсии, очевидно, заключается в возможности определения бесконечного множества объектов с помощью конечного утверждения. Таким же образом бесконечное количество вычислений может быть описано конечной рекурсивной программой, даже если эта программа не содержит явных повторений. Рекурсия (информатика)
Работа рекурсивных случаев можно рассматривать как разбиение сложных входных данных на более простые. В правильно спроектированной рекурсивной функции при каждом рекурсивном вызове проблема ввода должна быть упрощена таким образом, чтобы в конечном итоге был достигнут базовый случай. (Функции, которые не предназначены для завершения при нормальных обстоятельствах - например, некоторые системные и серверные процессы - являются исключением.) Пренебрежение написанием базового варианта или его неправильное тестирование может вызвать бесконечный цикл . Рекурсия (информатика)
Для некоторых функций (например, той, которая вычисляет ряд для e = 1/0! + 1/1! + 1/2! + 1/3! + ... ), не существует очевидного базового случая, подразумеваемого входными данными ; для них можно добавить параметр (например, количество добавляемых терминов в нашем примере с серией), чтобы обеспечить «критерий остановки», который устанавливает базовый вариант. Такой пример более естественно трактовать с помощью corecursion , где последовательные члены на выходе являются частичными суммами; это можно преобразовать в рекурсию, используя параметр индексации, чтобы сказать «вычислить n- й член ( n- я частичная сумма)». Рекурсия (информатика)
