|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Занятие 12. Рекурсия - 1.
Рекурсивный вызов - это вызов процедуры
(функции) из нее самой.
Рекурсивная процедура (функция) - это процедура (функция),
которая совершает рекурсивные вызовы.
Рекурсия - это способ реализации вычислительного
процесса, при котором решение задачи описывается с помощью
рекурсивной процедуры (функции).
Рассмотрим в качестве примера рекурсивную функцию вычисления факториала:
Function Fact(n : LongInt) : LongInt;
begin
if n=0 then Fact:=1
else Fact:=Fact(n-1)*n;
end;
В данной реализации мы каждый раз сводим нашу задачу к аналогичной задаче меньшей размерности с помощью простой формулы n! = (n-1)! * n до тех пор, пока решение не станет очевидным: 0! = 1.
При написании рекурсивной функции особое внимание следует обратить на два вопроса:
-
(a) Почему она всегда будет заканчивать работу?
(b) Почему она будет работать правильно, если закончит работу?
Чтобы проверить (a), обычно находят параметр, который
- уменьшается (увеличивается) с каждым рекурсивным вызовом
- не может уменьшаться (увеличиваться) до бесконечности
- уменьшение (увеличение) параметра всегда приводит к одному из крайних значений
- значение нашей функции при крайних значениях параметра известно либо легко вычисляется
Чтобы проверить (b), убедимся в корректности работы процедуры (функции), считая, что рекурсивные вызовы возвращают правильное значение. После этого корректность работы всей процедуры в целом будет доказана с помощью метода математической индукции(база индукции - правильное значение функции на крайних значениях параметра, переход нами только что обоснован).
Рекурсивная форма организации алгоритма зачастую оказывается изящнее нерекурсивной и дает более компактный текст программы, но работает, как правило, медленнее.
Примечание. В большинстве задач, предложенных в рамках этого занятия, введен искусственный запрет на использование циклов. Этот запрет предназначен для того, чтобы на простых задачах научить Вас применять рекурсию, без которой многие более сложные задачи вызовут большие трудности.
| Задача 12-1. N-ое число Фибоначчи |
| Задача 12-2. НОД |
| Задача 12-3. Генератор |
| Задача 12-4. Без массивов |