Здавалка
Главная | Обратная связь

Var a, b, c : Integer;



Function Sum(x, y : Integer) : Integer; x, y – параметры-значения

Begin

x := x + 1; изменение значений формальных

y := y + 1; параметров в функции

Sum := x + y;

End;

Begin

a := 1;

b := 1;

c := Sum(a, b);

WriteLn(‘a=’, a, ‘ b=’, b);

ReadLn;

End.

Входные значения фактических параметров x = 1, y = 1. После выполнения программы они останутся теми же, хотя внутри функции соответствующие им формальные параметры изменились,

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

 

Program Primer;

Uses CRT;

Var a, b, c : Integer;

Function Sum(Var x, y : Integer) : Integer; x, y – параметры-переменные

Begin

x := x + 1; изменение значений формальных

y := y + 1; параметров в функции

Sum := x + y;

End;

Begin

a := 1;

b := 1;

c := Sum(a, b);

WriteLn(‘a=’, a, ‘ b=’, b);

ReadLn;

End.

Входные значения фактических параметров x = 1, y = 1. После выполнения программы они изменятся и примут значения x = 2, y = 2.

При использовании параметров-переменных в функцию передаются не копии фактических параметров, как это имело место с параметрами-значениями, а адреса фактических параметров, что позволяет сохранять их измененные функцией значения.

Зачастую использование параметров-переменных может тоже привести к непредсказуемым результатам вычислений:

Program Primer;

Uses CRT;

Var a, b : Integer;

Function Nemo(Var x : Integer; y : Integer) : Integer;
x – параметр-переменная,

y – параметр-значение

Begin

x := x + y;

a := y;

Nemo := x;

End;

Begin

a := 1;

b := 2;

WriteLn(‘Nemo=’, Nemo(a, b),‘ a=’, a, ‘ b=’, b);

ReadLn;

End.

Результат работы программы:

Nemo=2 a=2 b=2

Значение переменной a будет испорчено, так как значения переменных a и x будут записываться в одной ячейке памяти, а функция Nemo вместо 3 примет значение, равное 2. Ошибки такого рада трудно найти, поэтому в функциях и не рекомендуется использовать параметры-переменные,

15. в заголовке функции нельзя использовать формальные параметры безымянных типов (стандартные типы считаются поименованными):

Function Func(x : 1..10; r : array [1..20] Of Real) : Real;

Типы формальных параметров x и r являются безымянными, так как не относятся к стандартным. Поэтому в вызывающей эту функцию программе необходимо определить новые типы данных:

Type TCount = 20;

TVector = Array [1 .. TCount] Of Real;

TInterval = 1 .. 10;

а в заголовке функции использовать эти новые типы:

Function Func(x : TInterval; r : TVector) : Real;

16. в любой функции в качестве формальных параметров могут быть использованы другие функции, составленные программистом – параметры-функции.
Требования к таким функциям:

ü их тип должен быть определен в разделе описания типов Type,

ü они не должны быть стандартными,

ü они не должны быть вложенными,

ü они должны иметь только параметры-значения,

ü они должны быть откомпилированы с использованием директивы компилятору {$F+} – использование дальнего типа вызова подпрограмм.

Пример: создать функцию для определения суммы, произведения двух чисел и произведения их суммы на их разность. Функции для выполнения этих операций описать как параметры-функции:

Program Param_func;

Uses CRT;

Type TFunс = Function (x, y: Integer): Integer; описан процедурный тип TFunc – целой функции двух аргументов целого типа

Var a, b, c: Integer;

{$F+} директива компилятору- использование дальнего типа вызова подпрограмм

Function Add(x, y: Integer): Integer; функция для сложения двух переменных

Begin

Add := x + y;

End;

Function Mult(x, y: Integer): Integer; функция для перемножения двух переменных

Begin

Mult := x * y;

End;

Function Funny(x, y: Integer): Integer;

Begin

Funny := (x + y) * (x - y);

End;

{$F-} отменадирективы

функция, использующая параметр-функцию operation

Function Par_func(m, n : Integer; operation : TFunc): Integer;

Begin

Par_func := operation(m, n);

End;

Begin

ClrScr;

a := 5;

b := 3;

c := Par_func(a, b, Add); фактические параметры для параметров-функций не указываются!

WriteLn('c=', c);

c := Par_func(a, b, Mult);

WriteLn('c=', c);

c := Par_func(a, b, Funny);

WriteLn('c=', c);

ReadLn;

End.

На экран будет выведено:

с=8

с=15

с=16

17. в Паскале разрешено использовать рекурсию – обращение функции самой к себе, при этом имя функции со списком формальных параметров будет стоять в операторах функции справа от знака присваивания.

 

Рекурсия

Использование рекурсии в программировании базируется на рекурсивных математических определениях. Считается, что в математике рекурсивность как принцип определений используется с 1890 года. Впервые применил ее Д.Гильберт.

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

Например, вычисление факториала целого неотрицательного числа n! = 1·2·3·…·(n-1) · n . Кроме того, по определению, 0! = 1. Рекурсивное математическое определение факториала имеет вид:

1 при n = 0,

n!=

(n – 1)!·n при n > 0.

Последовательность чисел Фибоначчи имеет вид 1, 1, 2, 3, 5, 8, 13…

В ней два первых числа фиксированы и равны единице, а каждое последующее число равно сумме двух предыдущих. Рекурсивное математическое определение числа Фибоначчи с порядковым номером n имеет вид:

1 при n = 1,

Fn= 1 при n = 2,

Fn-2 + Fn-1 при n > 2.

Общей особенностью этих рекурсивных определений является то, что некий сложный объект определяется через себя же (рекурсивно обращается к себе же), но в более простом исполнении. Рекурсивные математические определения отличаются особой лаконичностью, что и подтверждается вышеприведенными примерами.

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

Рассмотрим последовательность факториалов целых чисел 0!, 1!, 2!, 3!,…, в которой ai = i!, i = 1, 2, 3,… Эту же последовательность можно представить в виде рекуррентной формулы: ai = ai-1·i, a0 = 1, i = 1, 2, 3… Эта формула задает последовательность, в которой каждый очередной член зависит непосредственно от предшествующего. Начальный член последовательности a0 задан прямою. Найдя член последовательности с порядковым номером i = n, мы тем самым решим задачу вычисления n!

Рекуррентная формула для вычисления числа Фибоначчи с заданным порядковым номером i = n практически не отличается от рекурсивного определения: Fi = Fi-2 + Fi-1 , F1 = 1 , F2 = 1 , i = 3, 4, 5,…

Итак, функция считается рекурсивной, если при решении задачи она обращается к самой себе или непосредственно, или через другие подпрограммы. Известно, как технически реализуется обращение к подпрограмме в общем случае:

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

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

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

При рекурсивном обращении каждый раз приходится запоминать не только адрес возврата, но и всю совокупность данных вызывающей подпрограммы (локальные переменные и параметры-значения). С этой целью используется автоматически выделяемая область памяти – стек, структура, работающая по принципу LIFO (Last in – first out: последним пришел – первым вышел). Такой метод работы с памятью обеспечивает строгое соответствие прямого порядка записи данных обратному порядку их чтения. Только с помощью стека можно достаточно просто обеспечить корректное завершение работы цепочки подпрограмм, каждая из которых вызывает следующую: сначала должна быть завершена последняя, затем – предпоследняя и так далее. Максимальный размер стека – 65520 байт. Поэтому последовательность рекурсивных обращений не может быть бесконечной. В любой рекурсивной подпрограмме должна быть нерекурсивная (терминальная) ветвь, обеспечивающая выход из рекурсии. При переполнении стека работа программы прерывается, и появляется сообщение об ошибке Error 202: Stack overflow error.

Рекурсивная функция, вычисляющая факториал заданного числа n, может иметь вид:

Function Factorial(n: Word): Word;

Begin

If (n=0)

Then Factorial := 1 выход из рекурсии

Else Factorial := n * Factorial(n – 1); рекурсия

End;

При n = 5 эта функция будет работать следующим образом:

Factorial := 5 * Factorial(4)

5 * 4 * Factorial(3)

5 * 4 * 3 * Factorial(2)

5 * 4 * 3 * 2 * Factorial(1)

5 * 4 * 3 * 2 * 1 = 120

В данном случае реализована так называемая нисходящая рекурсия: вызов Factorial(5) означает, что функция Factorial вызывает себя раз за разом: Factorial(4), Factorial(3), … до тех пор, пока не будет достигнута терминальная ситуация – ситуация окончания рекурсии. При каждом вызове текущие вычисления откладываются, локальные переменные и адрес возврата остаются в стеке. Терминальная ситуация Factorial := 1 достигается при n = 0. При этом рекурсивный спуск заканчивается, начинается рекурсивный возврат изо всех вызванных в данный момент копий функции: начинает строиться ответ n*Factorial(n-1). Сохраненные локальные параметры выбираются из стека в обратной последовательности, а получаемые промежуточные результаты: 1*1, 2*1, 3*2*1, 4*3*2*1, 5*4*3*2*1 – передаются вызывающим функциям.

Рекурсивная функция, вычисляющая n-й член ряда Фибоначчи, может иметь вид:

Function Fibo(n: Word): Word;

Begin

If (n=1) Or (n=2)

Then Fibo := 1 выход из рекурсии

Else Fibo := Fibo(n-2) + Fibo(n-1); рекурсия

End;

Мы рассмотрели непосредственную рекурсию – функция вызывает саму себя. Помимо непосредственной, возможна косвенная рекурсия – функция Func_1 вызывает функцию Func_2, а функция Func_2, в свою очередь – функцию Func_1. Но как описать две функции, вызывающие одна другую? Ведь по правилам Паскаля подпрограмма обязательно должна быть объявлена до своего использования. В этом случае используется опережающее описание с помощью директивы Forward. При объявлении подпрограммы указывается только ее заголовок со списком формальных параметров и директивой Forward, а тело создается далее без повторного описания этих параметров:

Program Primer;

Uses CRT;

Var i: Integer; описание переменных головной программы

Function Func_1(x: Integer): Integer; Forward; опережающее объявление функции Func_1

Function Func_2(y: Integer): Integer; описание функции







©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.