Рекурсия
Рекурсия
— это такой способ организации вспомогательного алгоритма (подпрограммы), при
котором эта подпрограмма (процедура или функция) в ходе выполнения ее
операторов обращается сама к себе. Вообще, рекурсивным называется любой объект,
который частично определяется через себя.
Например,
приведенное ниже определение двоичного кода является рекурсивным:
::= |
::= 0 | 1
Здесь
для описания понятия были использованы, так называемые, металингвистический
формулы Бэкуса-Наура (язык БНФ); знак "::=" обозначает "по
определению есть", знак "|" — "или".
Вообще,
в рекурсивном определении должно присуствовать ограничение, граничное условие,
при выходе на которое дальнейшая инициация рекурсивных обращений прекращается.
Приведём
другие примеры рекурсивных определений.
Пример
1. Классический пример, без которого не обходятся ни в одном рассказе о
рекурсии, — определение факториала. С одной стороны, факториал определяется
так: n!=1*2*3*...*n. С другой стороны, Граничным
условием в данном случае является n