Циклы и рекурсивные процедуры
Рекурсия уже была использовано выше в примере описания понятия двоичный код с помощью металингвистических формул: <двоичный код>::=<двоичная цифра>|<двоичный код><двоичная цифра>;. В данном случае понятие определяется с использованием этого же понятия. Такое определение позволяет описать двоичный код произвольной длины (подразумевается циклическое приписывание двоичных цифр). Рекурсивным может быть и определение функции. Классическим примером является определение факториала. Эту функцию можно определить различными способами, в том числе и рекурсивно:
В данном случае n! определяется через (n-1)!, т.е. через эту же самую функцию. Данное определение также предполагает циклическое приписывание к произведению очередного множителя. Выше рассматривался пример вычисления факториала, который реализовывался с помощью циклического алгоритма. Очевидно, такой цикл можно организовать с помощью рекурсивного описания функции. В большинстве современных языков программирования такое описание функций и процедур разрешается. Особенность рекурсивного описания процедуры состоит в том, что в теле такой процедуры содержится обращение к описываемой процедуре.
|
.
