Rambler's Top100

Билет 15 . Вопрос 1.

Понятие прямой и косвенной рекурсии. Примеры. Реализация в языке Pascal.

 

Процедура или функция, вызывающая саму себя, называется рекурсивной .

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

В ряде случае рекурсивное оформление подпрограмм может быть более компактным и эффективным.

Рекурсивная программа должна иметь специальный "выход", для предотвращения зацикливания, которое приводить к переполнению памяти, отведённой под стек.

Рекурсия может быть как прямой , когда программа вызывает саму себя, так и непрямой( косвенной ) , когда программа вызывает другую программу, а та в свою очередь, вызывает первую программу. При объявлении процедур при непрямой рекурсии вторая процедура объявляется с ключевым словом языка forward.

 

Пример 1.

program ForwardDemo;

procedure Second; forward;

procedure First;

begin

Second;

end; { First }

procedure Second;

begin

First;

end; { Second }

begin { ForwardDemo }

First;

end. { ForwardDemo }

 

Если процедуру Second объявить без слова forward, то её нельзя вызывать в процедуре First. (Эта программа демонстрирует также как создаётся зацикливание программы, поскольку бесконечная цепь вызовов First--Second--First--Second очень скоро переполняет пространство, отведённое под стек.)

При использовании директивы forward сначала записывается полный заголовок первой подпрограммы. Тело этой подпрограммы заменяется директивой forward. Затем полностью описывается вторая подпрограмма, а уже после этого описывается первая подпрограмма. При этом можно записывать сокращенный заголовок подпрограммы, который включает слово PROCEDURE или FUNCTION и ее имя. Список формальных параметров и тип подпрограмм (если это подпрограмма-функция) не указывается.

Следующая программа демонстрирует рекурсию. Процедура StackInput вызывает саму себя; при каждом вызове, новая копия локальной переменной "C" заносится в стек.

При нажатии кл. Ввод (ASCII код: #13), стек становится открытым и выпускает в обратном порядке символы, имевшиеся в нём (занесённые с клавиатуры).

 

Пример 2.

program RecursionDemo;

uses Crt;

procedure StackInput;

var

C: char;

begin

C := ReadKey;

if C <> #13 then StackInput;

Write(C);

end; { StackInput }

begin { RecursionDemo }

StackInput;

end. { RecursionDemo }

Пример 3. Вариант функции, рекурсивно вычисляющей факториал числа N,

function Factorial (N: Byte) : longint;

begin

if N in [0..1]

then Factorial:=1

else Factorial:=N* Factorial(N-1)

end;

Вверх

Белорусский рейтинг MyMinsk.com Сайты беларуси Регистр "ЗУБР" Каталог на TIGA.BY, а также  новости, работа, объявления, фото и многое другое Рейтинг@Mail.ru Rambler's Top100 Белорусский каталог программ Faststart - рейтинг сайтов, каталог интернет ресурсов, счетчик посещаемос­ти Яндекс.Метрика
Hosted by uCoz