ПРАКТИЧЕСКОЕ ЗАНЯТИЕ РАЗРАБОТКА ПРОГРАММ С ИСПОЛЬЗОВАНИЕМ РЕКУРСИВНЫХ ФУНКЦИЙ

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ РАЗРАБОТКА ПРОГРАММ С ИСПОЛЬЗОВАНИЕМ

РЕКУРСИВНЫХ ФУНКЦИЙ

1.     ЦЕЛЬ ЗАНЯТИЯ

Целью занятия является знакомство с рекурсивными функциями, областью их использования.

2.     ИНФОРМАЦИОННЫЙ БЛОК

В языке Паскаль процедуры и функции могут быть рекурсивными. Под- программа называется рекурсивной, если она вызывает саму себя. Рекурсивным может быть описание подпрограммы или обращение к ней.

Для того чтобы такое обращение не было бесконечным, в тексте подпро- граммы должно быть условие, по достижению которого дальнейшее обращение к подпрограмме не происходит.

Пример.

Рассмотрим математическую головоломку из книги Ж. Арсака «Програм-

мирование игр и головоломок».

Построим последовательность чисел следующим образом: возьмем целое число i>1. Если i -четное, то следующий член последовательности равен i/2, иначе он равен 3*i+1. Если i=1, то последовательность останавливается.

Математически конечность последовательности независимо от начального

i не доказана, но на практике последовательность останавливается всегда.

Применение рекурсии позволило решить задачу без использования циклов,

как в основной программе, так и в процедуре.

Пример программы с использованием рекурсии

Program Arsac;

Var first: word;

Procedure posledov (i: word); Begin

Writeln (i);

If i=1 then exit;

If odd(i) then posledov(3*i+1) else posledov(i div 2); End;

Begin

Write (‘ введите первое значение ’); readln (first); Posledov (first);

Readln ; End.

Программист разрабатывает программу, сводя исходную задачу к более простому способу решения. Среди этих задач может оказаться и первоначаль- ная, но в упрощенной форме. Например, для вычисления F(N) может понадо- биться вычислить предыдущее значение F(N-1). Иными словами, частью алго- ритма вычисления функции будет вычисление этой же функции.

Алгоритм, который является своей собственной частью, называется рекур- сивным. Часто в основе такого алгоритма лежит рекурсивное определение.

Пример рекурсивного алгоритма

N! = ( N-1)!* N, если N=0, то N!= 1

Любое рекурсивное определение состоит из двух частей. Одна часть опре- деляет понятие через него же, другая часть – через иные понятия.

Пример рекурсивного алгоритма:

2n= 2 n-1*2, если n=0, то 2 n= 1

Заметим, что при косвенном обращении все процедуры в цепочке – рекур- сивные.

Все сказанное о процедурах целиком относится и к функциям. Пример рекурсивной функции вычисления факториала Function factorial(N: integer) : longint;

Begin

If N= 0 then Factorial := 1

Else Factorial := factorial(N-1) * N End;

3.     ИСПОЛНИТЕЛЬНЫЙ БЛОК

Задание 1. Наберите текст программы из примера про математическую го- ловоломку из книги Ж. Арсака «Программирование игр и головоломок» (см. информационный блок). Запустите ее на выполнение, проверьте правильность работы программы.

Задание 2. Решите предыдущую задачу без использования рекурсивной процедуры, т.е. с использованием цикла.

Задание 3. Напишите рекурсивную функцию. Вывести на экран первые N

чисел Фибоначчи.

4.     КОНТРОЛЬНЫЕ ВОПРОСЫ

1)       Какую процедуру можно назвать рекурсивной?

2)       Можно ли заменить рекурсивную процедуру обычным циклом? Приве- дите пример решения задачи через рекурсивную процедуру и без нее.

3)       Приведите пример рекурсивной функции.