Пример 1. Рекурсивные описания алгоритмов

Рекурсивные описания алгоритмов.

Технология программирования на языках проце­ду­р­ного программирования (типа языка Паскаль) предла­гает проекти­ровать программы методом последо­ва­тельных уточнений.

Концепция процедур и функций (подпрограмм) позволяет выделить подзадачу как явную подпрограмму и оформить ее в виде процедуры или функции. Таким образом, программа представляет собой структуру, элементами которой являются процедуры и функции – основные семантические единицы программы.

В частности, в качестве подзадачи может фигу­ри­ро­вать и исходная задача с измененными исход­ными данны­ми (задача «меньшего размера»).

Поиск минимального элемента в последо­ва­тельности

a₁, a₂,.., a_k, a_k+1,.., a_n

можно организовать как

* поиск минимального элемента b₁ в a₁, a₂,.., a_k;

* поиск минимального элемента b₂ в a_k+1, a_k+2,.., a_n;

* выбор наименьшего элемента b из двух найденных (b₁, b₂).

Основная идея состоит в том, чтобы разбить последова­тель­ность на две части a₁, a₂,.., a_k и a_k+1, a_k+2,.., a_n , применить описываемый метод к каждой из этих частей, а затем выбрать наименьший элемент из двух найденных. Такие алгоритмы называют рекурсивными.

Описание процедуры (функции) P, в разделе опера­торов которой используется оператор этой процедуры (вызов функции), называется рекурсивным.

Рис. 1. Схема простой рекурсии

Использование рекурсивного описания процедуры (функ­ции) приводит к рекурсивному выполнению этой процедуры (вычислению этой функции).

Пример 2. Факториал.

Рассмотрим рекурсивное определение факториала натурального числа n - функции n! = 1*2*...*n. Пусть F(n) = n!! Тогда

1.F(0) = 1

2.F(n) = n*F(n - 1) при n > 0

Средствами языка это определение можно сформу­ли­ровать как вычисление:

If n = 0

then F:= 1

else F:= F(n - 1) * n

Оформив это вычисление как функцию, получим:

Function F(n: Integer): Integer;

Дата добавления: 2014-01-06