Билет 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; |