Рекурсивные подпрограммы

Слово рекурсия происходит от латинского слова «recursio» – возвращение.

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

Известными рекурсивными подпрограммами являются вычисление факториала (рисунок 2.8), решение задачи о Ханойских башнях, быстрая сортировка К.Хоара, подпрограммы работы с динамическими структурами данных, подпрограммы построения фракталов и многие другие.

Пример рекурсивной подпрограммы:

Рисунок 2.8 –Рекурсивная подпрограмма вычисления 3!

Главные требования к организации рекурсивной подпрограммы следующие:

§ рекурсивная подпрограмма имеет хотя бы один параметр

§ рекурсивная подпрограмма всегда содержит условие завершения рекурсии и, если это условие не выполняется, подпрограмма вызывает сама себя с изменением значения параметра.