Рекурсивный алгоритм решения задачи

В программировании рекурсия — вызов функции из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция вызывает функцию , а функция — функцию . Количество вложенных вызовов функции или процедуры называется глубиной рекурсии. Рекурсивная программа позволяет описать повторяющееся или даже потенциально бесконечное вычисление, причём без явных повторений частей программы и использования циклов.

Структурно рекурсивная функция на верхнем уровне всегда представляет

собой команду ветвления (выбор одной из двух или более альтернатив в

зависимости от условия (условий), которое в данном случае уместно назвать

«условием прекращения рекурсии»), имеющей две или более альтернативные

ветви, из которых хотя бы одна является рекурсивной и хотя бы одна —

терминальной. Рекурсивная ветвь выполняется, когда условие прекращ

ения рекурсии ложно, и содержит хотя бы один рекурсивный вызов —

прямой или опосредованный вызов функцией самой себя. Терминальная

ветвь выполняется, когда условие прекращения рекурсии истинно; она

возвращает некоторое значение, не выполняя рекурсивного вызова.

Правильно написанная рекурсивная функция должна гарантировать, что

через конечное число рекурсивных вызовов будет достигнуто выполнение

условия прекращения рекурсии, в результате чего цепочка последовательных

рекурсивных вызовов прервётся и выполнится возврат.

Помимо функций, выполняющих один рекурсивный вызов в каждой

рекурсивной ветви, бывают случаи «параллельной рекурсии», когда на одной

рекурсивной ветви делается два или более рекурсивных вызова.

Параллельная рекурсия типична при обработке сложных структур данных,

таких как деревья. Простейший пример параллельно-рекурсивной

функции — вычисление ряда Фибоначчи, где для получения значения n-го

члена необходимо вычислить (n-1)-й и (n-2)-й.

ОПИСАНИЕ ПРОГРАММ