Побочный эффект рекурсии
Пример.
Пример.
Итерация и рекурсия
Стандартные функции
Они вам известны: это арифметические, алгебраические и тригонометрические функции. Кроме того, есть функция конца строки: Eoln - end of line.
Итерация (от лат. повторение) - повторение, применение какой – либо математической.
Пример: Вычислить сумму ряда:
S=a1+a2+….+an
S1=a1
S2=a1+a2
S3=a1+a2+a3
S4=a1+a2+a3+a4
…………………
S=a1+a2+…+an
Рекурсия (от лат. возвращение) - вычисление последующего значения ряда через предыдущее. Последовательность, в которой соседние значения связаны формулой, называется рекурсивной.
Пример: Арифметическая прогрессия: a1, a2=a1+d, a3=a2+d, an=an-1+d
Begin
If (n=0) or (n=1) then Factorial:=1
Else begin F:=1
For i:=2 to n do
F:=f*i;
Factorial:=f;
End;
End;
Begin Writeln (‘Введите N’);
Readln (N);
Writeln (‘факториал=’,Fact);
End.
Program Rekursion;
Var fact:real;
N:integer;
Function Factorial (N:integer):real;
Begin
If (n=0) or (N=1) then factorial:=1
Else factorial:=factorial (N-1)*n;
End;
Begin
writeln (‘Введите N’);
Readln (N);
Fact:=factorial (N);
Writeln (‘факториал=’,fact);
End.
Здесь первый вызов функции происходит в основной программе, а затем, начинается рекурсивный вызов внутри функции.
В языке программирования Паскаль есть возможность обращения процедуры или функции к самой себе. При этом циклическую часть программы можно составить без операторов цикла. Способ обращения процедуры или функции к самой себе называется рекурсией. С помощью рекурсии удобно представлять те задачи, которые сводятся к подзадачам того же типа, но меньшей размерности.
Вычисление факториала можно представить опять через факториал.
N!=n(n-1)!-рекурсивная формула.
Представление факториала в виде последовательности операций умножения – это итерационный процесс. n!= 1*2*3…n-итерационная формула. Итерация программируется с помощью циклов.
Пример: Вычисление факториала.
Program Iteracion ;
Var fact: real;
N:integer;
Function factorial (n: integer):real;
Var f:real;
I: integer;
Пример. В 13 веке итальянский математик Фибоначчи сформулировал задачу: ”Некто поместил пару кроликов в некое место, огороженное со всех сторон стеной, чтобы узнать, сколько пар кроликов родится в течении года, если через месяц пара кроликов производит на свет другую пару, а рожают со второго месяца после своего рождения.
Program Krolik;
Var kr:integer; (*число кроликов*)
N:Integer; (*число месяцев*)
Function fib(n:integer):integer;
Begin
If (n=1) or (n=2) then fib:=1
Else fib:=fib(n-1)+fib(n-2)
End;
Begin
Writeln(‘ввести N’);
Readln (N);
Kr:=fib (N); (*вызов ф-и*)
Writeln (kr:5);
End.
В теле подпрограммы известны, то есть доступны все объекты, описанные в объемлющем блоке, в том числе и имя самой подпрограммы. Внутри тела подпрограммы возможен вызов самой подпрограммы. Параметры и функции использующие вызовы “самих себя“, называются рекурсивными. Допустима также косвенная рекурсия, при которой параметр А вызывает параметр В, а тот, в свою очередь, вызывает С, который вызывает первоначальный параметр А.
Рекурсия достаточно широко применяется в программировании, что основано на рекурсивной природе многих математических алгоритмов. В языке программирования Паскаль нет никаких ограничений на рекурсивные вызовы подпрограмм, необходимо только понимать, что каждый очередной рекурсивный вызов приводит к образованию новой копии локальный объектов подпрограммы и все эти копии, соответствующие цепочке активизированных и не активизированных рекурсивных вызовов, существующих независимо друг от друга.
При выполнении функций возникает один неожиданный эффект, причиной которого является изменение значений нелокальных переменных в теле функции.
Если в некоторой функции имеются конструкции, например, операторы присваивания, изменяющие значения переменных, описанных в объемлющих блоках, то может возникнуть ситуация, при которой значения выражения, использующего вызов такой функции, зависит от порядка следования операторов, что является потенциальным источником ошибок и поэтому крайне нежелательно. Описанная ситуация называется побочным эффектом рекурсии.
Пример:
Program Side Effect;
Var a,z :integer;
Function change (x: integer): integer;
Begin
Z:=z-x; {изменяем значение нелокальной переменной}
Change:= sqr (x)
End;
Begin
Z:=10; a:=change (z); writeln(a,z);
Z:=10; a:=change (10)*change (z);
Writeln(a,z);
Z:=10; a:=change (z) * change(10);
Writeln (a,z)
End.
Выполнение этой программы приводит к следующему результату на дисплее:
100 0
10000 -10
0 0
Т.е. два последних присваивания переменной а дают различный результат, хотя правила вычисления выражений предлагают равноправные сомножители.
Следует всячески избегать такой зависимости функции от глобальных по отношению к ней переменных. Заметим, что современные языки, например, Ada содержит прямые запреты на подобные действия.
Предварительное описание (ссылки вперед)
Объявления констант и переменных в любом блоке располагаются перед скобками begin ...end (в этих скобках заключены сами операторы). Поэтому компилятору никогда не приходится иметь дело с оператором, содержащим константы и переменные, которых он не знает, это вызовет во время компиляции сообщение об ошибке. Все это справедливо и в отношении подпрограмм (т.е. функций и процедур). Программист обязан следить за правильным порядком следования определений (описаний).
Пример :
Program Demo;
Var a, b ,c : real ;
Procedure Ring (var s , l : real ; d : real);
Begin L:=3.14 *d; {длина окружности }
S:=cir (d) ; {компилятор еще не знает о функции cir}
End;
Function Cir (d: real): real; {площадь круга }
Begin cir:= 3.14* sqr(d) / 4;
End;
………………………………………………………………………
Очевидный выход – поменять порядок строк так, чтобы функция Cir была определена перед процедурой Ring(…) .Однако можно и иначе.
Действия:
1. Оставить подпрограмму (функцию cir) на своем месте, вычеркнув из ее заголовка все параметры: Function cir;
2. Вставить полный заголовок там, где ему надлежит бытью, т.е. перед подпрограммой, которая его вызывает.
Function cir (d: real): real;
1. После полного заголовка добавить слово Forward.