Косвенная рекурсия

Оглавление

Рекурсия. 1

Формы рекурсивных процедур. 2

Рекурсивный спуск. 3

Комбинация прямой и обратной рекурсии. 4

Косвенная рекурсия. 5

Контрольные вопросы.. 5

Комбинированный урок №14-15

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

Program Factorial;

Var

Fact : Longint;

n, i : Integer;

Begin

Write ('Введите число n: ');

Readln ( n );

Fact := 1;

for i:= 1 to n do Fact := Fact*i;

Writeln ('Факториал n! = ', Fact);

End.

Однако существует также другое определение факториала, в котором используется рекуррентная формула и которое имеет такой вид:

(1) 0! = 1

(2) для любого n > 0 n! = n * (n - 1)!

Определения с помощью рекуррентных формул иногда называют рекурсивными определениями. Если для факториала первое (итеративное) определение может показаться проще, то для чисел Фибоначчи рекурсивное определение:

(1) F(1) = 1,

(2) F(2) = 1,

(3) для любого n > 2 F(n) = F(n-1) + F(n-2)

выглядит для вычислений лучше, чем прямая формула:

Похожие рекуррентные формулы есть также и для многих других математических определений. Понятно, что организовать вычисления по рекуррентным формулам можно и без использования рекурсии. Использование рекурсии позволяет легко (почти дословно) запрограммировать вычисления по рекуррентным формулам. Например, программа, использующая рекурсивную функцию для вычисления факториала n! имеет следующий вид:

Program Factorial;

Var

N : Integer;

function Fact ( i : Integer ): Longint;

Begin

if i = 1 then Fact := 1

else Fact := i * Fact (i-1)

End;

Begin

Write ('Введите число n: ') ;

Readln (n);

Writeln ('Факториал n! = ', Fact(n));

End.

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

Для создания рекурсивных алгоритмов необходимо и достаточно наличие понятия процедуры или функции. Это вытекает из того, процедуры и функции позволяют дать любой последовательности действий (операторов) имя, с помощью которого можно будет эту последовательность действий вызывать.

Например, следующая процедура будет бесконечно печатать известные всем строки:

Program EndLess1;

Procedure PopeAndDog1;

Begin

Writeln('У попа была собака, он ее любил.');

Writeln('Она съела кусок мяса, он ее убил,');

Writeln('похоронил и надпись написал:');

PopeAndDog1

End;

Begin

PopeAndDog1

End.

Однако если оператор вызова процедуры поставить перед выводом текста, как показано ниже:

Program EndLess2;

Procedure PopeAndDog2;

Begin

PopeAndDog2;

Writeln('y попа была собака, он ее любил.');

Writeln('Oнa съела кусок мяса, он ее убил,');

Writeln('похоронил и надпись написал:');

End;

Begin

PopeAndDog2

End.

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

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

Однако за эту простоту приходится расплачиваться неэкономным использованием оперативной памяти, так как выполнение рекурсивных процедур требует значительно большего размера оперативной памяти во время выполнения, чем не рекурсивных. При каждом рекурсивном вызове для локальных переменных, а также для параметров процедуры, которые передаются по значению, выделяются новые ячейки памяти. Максимальное число рекурсивных вызовов процедуры без возвратов, которое происходит во время выполнения программы, называется глубиной рекурсии. Число рекурсивных вызовов в каждый конкретный момент времени, называется текущим уровнем рекурсии.

Формы рекурсивных процедур

Как было показано на предыдущем шаге, безусловные рекурсивные процедуры приводят к бесконечным процессам, и на эту проблему нужно обратить особое… Следовательно, главное требование к рекурсивным процедурам заключается в том,… Если условие истинно, то рекурсивный спуск продолжается. Когда оно становится ложным, то спуск заканчивается и…

Procedure Rec;

Begin

S; {операторы}

If <условие> then Rec;

End;

2. Форма с выполнением действий после рекурсивного вызова (с выполнением действий на рекурсивном возврате):

Procedure Rec;

Begin

if <условие> then Rec;

S; {операторы}

End;

3. Форма с выполнением действий как до, так и после рекурсивного вызова (с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате):

Procedure Rec;

Begin

S1;

if <условие> then Rec;

S2;

End;

Или

Procedure Rec;

Begin

if <условие> then

Begin

S1;

Rec;

S2;

End;

End;

Все формы рекурсивных процедур находят применение на практике. Многие задачи, в том числе вычисление факториала, безразличны к тому, какая используется форма рекурсивной процедуры. Однако есть классы задач, при решении которых программисту требуется сознательно управлять ходом работы рекурсивных процедур и функций. Поэтому глубокое понимание рекурсивного механизма, и умение управлять им по собственному желанию, является необходимым качеством квалифицированного программиста.

Первые две формы рекурсивных подпрограмм рассмотрим на примере вычисления факториала (n!), третью форму - на примере реверсивной печати вводимой строки.

Рекурсивный спуск

Mult - для выполнения до рекурсивного вызова (то есть на спуске) операции умножения накапливаемого значения факториала на очередной множитель; m - для обеспечения независимости рекурсивной функции от имени конкретной… Программа Factorial_Down, которая использует рекурсивную функцию Fact_Dn, выполняющую вычисления на спуске, имеет…

Program Factorial_Down;

var n : Integer;

function Fact_Dn(Mult : Longint; i, m : Integer ) :Longint;

Begin

Mult := Mult * i;

{ Накопление факториала стоит до оператора рекурсивного вызова.}

{ Следовательно вычисление выполняется на спуске. }

if i = m then Fact_Dn := Mult

else Fact_Dn := Fact_Dn (Mult, i+1, m)

End;

Begin

Write ('Введите число n: ');

Readln ( n );

Writeln ('Факториал n! = ' , Fact_Dn(1,1,n ));

End.

Для демонстрации выполняемых функцией Fact_Dnдействий приведем таблицу трассировки значений ее параметров по уровням рекурсии. В этой таблице рассмотрен конкретный случай для n = 5.

 

Рис.1. Трассировка значений параметров

 

Рассмотренная выше программа Factorial, использующая рекурсивную функцию Fact, выполняет вычисление факториала на возврате. Но это не совсем очевидно, поскольку в функции Factрекурсивный вызов и операция умножения совмещены в одном операторе присваивания. Для более понятной демонстрации работы на возврате, приведем программу Factorial_Up, использующую функцию Fact_Up, в которой рекурсивный вызов и оператор накопления факториала разделены явным образом.

Program Factorial_Up;

Var

N : Integer;

function Fact_Up(i :Integer) : Longint;

Var

Mult: Longint;

Begin

if i = 1 then Mult := 1

else Mult := Fact_Up (i-1);

Fact_Up := Mult * i {Накопление факториала стоит после }

{оператора рекурсивного вызова. }

{Следовательно вычисление выполняется на возврате. }

End;

Begin

Write ( 'Введите число n: ');

Readln (n);

Writeln ('Факториал n! = ', Fact_Up (n));

End.

Приведем таблицу трассировки по уровням рекурсии, аналогичную таблице для функции Fact_Dn:

Рис.2. Трассировка значений параметров

Комбинация прямой и обратной рекурсии

Задача. Вывести на печать символы введенной строки 'HELLO' в обратном направлении. Решение этой задачи выполнено в виде показанной ниже программы…

Program Reverse_String;

Procedure Reverse;

Var

Ch : Char;

Begin

If not EoLn then

Begin

Read (Ch) ;

Reverse;

Write (Ch);

End

End;

Begin

Reverse

End.

Если после запуска программы на выполнение в качестве входной строки ввести слово 'HELLO', то соответствующая такой исходной строке таблица трассировки по уровням рекурсии будет иметь следующий вид:

Рис.3. Трассировка значений параметров

Косвенная рекурсия

Косвенной или взаимной рекурсией называется организация вызовов нескольких процедур и функций по кругу (первая процедура вызывает вторую, вторая - третью, ..., n-я процедура вызывает первую).

Для реализации косвенной рекурсии при описании процедур и функций используется директива forward:

Program Recurs;

procedure Rec1 (i : Byte); forward;

procedure Rec2 (i : Byte);

Begin

Writeln ('рекурсия.');

Rec1(i)

End;

Procedure Rec1;

Begin

if i > 0 then

Begin

Write ('Взаимная ');

Rec2 (i-1)

End

End;

Begin

Reс1 (5)

End.

Результат:

Взаимная рекурсия.

Взаимная рекурсия.

Взаимная рекурсия.

Взаимная рекурсия.

Взаимная рекурсия.

 

 

Контрольные вопросы

1. Дайте определение рекурсии.

2. Какие формы принимает рекурсивная процедура? Приведите примеры.

3. Что такое рекуррентное выражение? Приведите примеры.

4. Дайте определение прямой и косвенной рекурсии.