Язык программирования Pascal. Процедуры и функции. Рекурсия. Васильев В.В - 21 стр.

UptoLike

21
writeln('Искомый интеграл равен ',I:8:4);
readkey
End. {Runge}
Проверьте работу программы на ПК!
3. Рекурсивные подпрограммы
Процедуры и функции, которые вызывают сами себя, называются рекур-
сивными.
Рекурсивные объекты частично определяются через самих себя. То есть
рекурсивные алгоритмы появляются , когда решение задачи для случая n выра-
жается через решение задачи для случая n-1.
Например , факториал можно определить с помощью рекуррентной форму-
лы :
0! = 1, n! = n * (n-1)!
Рекурсивная функция для вычисления n! может быть такой :
function fact (n:byte) :integer;
begin
if n=0
then fact:=1
else fact:=n*fact(n-1)
end;
Решение задачи , реализуемое рекурсивным алгоритмом , можно выразить
нерекурсивным алгоритмом . Например , n! можно вычислить так:
function fact_ (n:byte) :integer;
var i, k:integer;
begin
k:=1;
for i:=2 to n do k:=i*k;
fact_:=k
end;
Рекурсивные процедуры и функции просты , наглядны и компактны . Одна-
ко рекурсивные процедуры и функции требуют большего размера оперативной
памяти во время выполнения , чем нерекурсивные.
Значения всех локальных переменных и параметров , передаваемых по
значению , при очередном вызове рекурсивной процедуры или функции поме-
щаются в стек .
Стеком называется структура, напоминающая трубку с запаянным кон -
цом . При заполнении стека действует принцип «первым пришел, последним
ушел» . Если стек заполняется 1-м, 2-м, 3-м элементами, то извлекаться эти
элементы будут в обратном порядке 3-й, 2-й, 1-й.
То есть одной локальной переменной на разных уровнях рекурсии будут
соответствовать разные ячейки памяти.
Глубина рекурсии максимальное число рекурсивных вызовов проце-
дуры . Текущий уровень рекурсии количество рекурсивных вызовов в те-
кущий момент времени .