Программирование Часть 5 Функции

4. Структурное программирование Функции Структурная декомпозиция программы int main() { … input_vect (a,n); … add_vect (a,b,c,n); … output_vect (c,n); … return 0 } void input_vect (double v [ ], int dim) { … return; } void add_vect (double v1 [ ], double v2 [ ], double res [ ], int dim) { … return; } void output_vect (double v [ ], int dim) { … return; } Выполнение начинается с main Возврат из main в ОС

4. Структурное программирование Функции Структурная декомпозиция программы int main() { … input_vect (a,n); … add_vect (a,b,c,n); … output_vect (c,n); … return 0 } void input_vect (double v [ ], int dim) { … return; } void add_vect (double v1 [ ], double v2 [ ], double res [ ], int dim) { … return; } void output_vect (double v [ ], int dim) { … return; } Выполнение начинается с main Возврат из main в ОС

4. Структурное программирование Функции Структурная декомпозиция программы int main() { … input_vect (a,n); … add_vect (a,b,c,n); … output_vect (c,n); … return 0 } void input_vect (double v [ ], int dim) { … return; } void add_vect (double v1 [ ], double v2 [ ], double res [ ], int dim) { … return; } void output_vect (double v [ ], int dim) { … return; } Выполнение начинается с main Возврат из main в ОС

4. Структурное программирование Функции Структурная декомпозиция программы int main() { … input_vect (a,n); … add_vect (a,b,c,n); … output_vect (c,n); … return 0 } void input_vect (double v [ ], int dim) { … return; } void add_vect (double v1 [ ], double v2 [ ], double res [ ], int dim) { … return; } void output_vect (double v [ ], int dim) { … return; } Выполнение начинается с main Возврат из main в ОС

4. Структурное программирование Функции Структурная декомпозиция программы int main() { … input_vect (a,n); … add_vect (a,b,c,n); … output_vect (c,n); … return 0 } void input_vect (double v [ ], int dim) { … return; } void add_vect (double v1 [ ], double v2 [ ], double res [ ], int dim) { … return; } void output_vect (double v [ ], int dim) { … return; } Выполнение начинается с main Возврат из main в ОС

4. Структурное программирование Функции Структурная декомпозиция программы int main() { … input_vect (a,n); … add_vect (a,b,c,n); … output_vect (c,n); … return 0 } void input_vect (double v [ ], int dim) { … return; } void add_vect (double v1 [ ], double v2 [ ], double res [ ], int dim) { … return; } void output_vect (double v [ ], int dim) { … return; } Выполнение начинается с main Возврат из main в ОС

4. Структурное программирование Функции Структурная декомпозиция программы int main() { … input_vect (a,n); … add_vect (a,b,c,n); … output_vect (c,n); … return 0 } void input_vect (double v [ ], int dim) { … return; } void add_vect (double v1 [ ], double v2 [ ], double res [ ], int dim) { … return; } void output_vect (double v [ ], int dim) { … return; } Выполнение начинается с main Возврат из main в ОС

4. Структурное программирование Функции Структурная декомпозиция программы int main() { … input_vect (a,n); … add_vect (a,b,c,n); … output_vect (c,n); … return 0 } void input_vect (double v [ ], int dim) { … return; } void add_vect (double v1 [ ], double v2 [ ], double res [ ], int dim) { … return; } void output_vect (double v [ ], int dim) { … return; } Выполнение начинается с main Возврат из main в ОС

4. Структурное программирование Функции Структурная декомпозиция программы int main() { … input_vect (a,n); … add_vect (a,b,c,n); … output_vect (c,n); … return 0 } void input_vect (double v [ ], int dim) { … return; } void add_vect (double v1 [ ], double v2 [ ], double res [ ], int dim) { … return; } void output_vect (double v [ ], int dim) { … return; } Выполнение начинается с main Возврат из main в ОС

4. Структурное программирование Функции Структурная декомпозиция программы int main() { … input_vect (a,n); … add_vect (a,b,c,n); … output_vect (c,n); … return 0 } void input_vect (double v [ ], int dim) { … return; } void add_vect (double v1 [ ], double v2 [ ], double res [ ], int dim) { … return; } void output_vect (double v [ ], int dim) { … return; } Выполнение начинается с main Возврат из main в ОС

4. Структурное программирование Функции Структурная декомпозиция программы int main() { … input_vect (a,n); … add_vect (a,b,c,n); … output_vect (c,n); … return 0 } void input_vect (double v [ ], int dim) { … return; } void add_vect (double v1 [ ], double v2 [ ], double res [ ], int dim) { … return; } void output_vect (double v [ ], int dim) { … return; } Выполнение начинается с main Возврат из main в ОС

4. Структурное программирование Функции Структурная декомпозиция программы int main() { … input_vect (a,n); … add_vect (a,b,c,n); … output_vect (c,n); … return 0 } void input_vect (double v [ ], int dim) { … return; } void add_vect (double v1 [ ], double v2 [ ], double res [ ], int dim) { … return; } void output_vect (double v [ ], int dim) { … return; } Выполнение начинается с main Возврат из main в ОС

4. Структурное программирование Функции Структурная декомпозиция программы int main() { … input_vect (a,n); … add_vect (a,b,c,n); … output_vect (c,n); … return 0 } void input_vect (double v [ ], int dim) { … return; } void add_vect (double v1 [ ], double v2 [ ], double res [ ], int dim) { … return; } void output_vect (double v [ ], int dim) { … return; } Выполнение начинается с main Возврат из main в ОС

4. Структурное программирование Функции Структурная декомпозиция программы int main() { … input_vect (a,n); … add_vect (a,b,c,n); … output_vect (c,n); … return 0 } void input_vect (double v [ ], int dim) { … return; } void add_vect (double v1 [ ], double v2 [ ], double res [ ], int dim) { … return; } void output_vect (double v [ ], int dim) { … return; } Выполнение начинается с main Возврат из main в ОС

4. Структурное программирование Функции Структурная декомпозиция программы int main() { … input_vect (a,n); … add_vect (a,b,c,n); … output_vect (c,n); … return 0 } void input_vect (double v [ ], int dim) { … return; } void add_vect (double v1 [ ], double v2 [ ], double res [ ], int dim) { … return; } void output_vect (double v [ ], int dim) { … return; } Выполнение начинается с main Возврат из main в ОС

Функция – изолированный именованный блок кода, имеющий определенное назначение Информация в функцию передается с помощью аргументов (фактических параметров), задаваемых при ее вызове. Эти аргументы должны соответствовать формальным параметрам, указанным в описании функции. 4. Структурное программирование Функции int k = add_ints (2,3); int add_ints (int a, int b) { return a+b; } аргументы формальные параметры Значения аргументов заменяют соответствующие параметры в определении функции Возвращается значение 5

Структура функций Тип_Возврата Имя_функции ( список_параметров ) { операторы; return выражение ; } Область видимости параметров функции, объявленных в ее заголовке и переменных, объявленных в ее теле, ограничивается блоком тела функции. Эти переменные, если они не объявлены с атрибутом static уничтожаются после завершения выполнения функции, а хранимые ими значения безвозвратно теряются. Если функция не возвращает значения, в качестве типа возврата указывается void, а оператор return не содержит выражения, значение которого должно быть возвращено в вызываемую функцию. 4. Структурное программирование Функции Заголовок Тело функции

Прототипы функций К моменту вызова функции компилятор должен иметь информацию о ней, чтобы скомпилировать правильно ее вызов. Если текст функции размещен в файле с исходным текстом после ее вызова или вообще размещен в другом файле, необходимо объявить функцию с помощью оператора, называемого прототипом функции. Все прототипы функций обычно помещаются в начале исходного файла программы. Заголовочные файлы, включаемые для использования стандартных библиотечных функций, помимо прочего включают в себя прототипы этих функций. Описание прототипа ничем не отличается от описания заголовка функции: Тип_Возврата Имя_функции ( список_параметров ); Описание прототипа, в отличие от заголовка, заканчивается точкой с запятой. 4. Структурное программирование Функции

void input_vect(double v[ ],int n); void output_vect(double v[ ],int n); int main() { const int m=5; double x[5]; input_vect(x,m); output_vect(x,m); return 0; } void print_vector (double v[ ], int n) { cout

Способы передачи данных в вызываемую функцию Путем передачи аргументов функции С использованием глобальных переменных Через файлы на внешних запоминающих устройствах Способы передачи данных из вызываемой функции Через возвращаемое значение Через формальные параметры, вызываемые по ссылке Путем изменения значений глобальных переменных Через файлы на внешних запоминающих устройствах Кроме того, функция может выполнять какое-либо действие, не требующее передачи из нее данных в вызывающую функцию 4. Структурное программирование Функции

Передача аргументов в функцию по значению В С++ используются два механизма передачи аргументов в функцию: по значению и по ссылке. При передаче по значению в функции создаются копии аргументов с именами формальных параметров. Значения аргументов копируются в созданные переменные. По завершении работы функции обратное копирование из формальных параметров в переменные - аргументы не производится. Если в теле функции значения формальных параметров были изменены, эти изменения по завершении работы функции будут потеряны и никак не отразятся на значениях фактических параметров. По умолчанию все аргументы, кроме массивов, передаются в функции по значению 4. Структурное программирование Функции

int my(int i); int main() { int k=3, m=0; m=my(k); cout

int my(int i); int main() { int k=3, m=0; m=my(k); cout

int my(int i); int main() { int k=3, m=0; m=my(k); cout

int my(int i); int main() { int k=3, m=0; m=my(k); cout

int my(int i); int main() { int k=3, m=0; m=my(k); cout

int my(int i); int main() { int k=3, m=0; m=my(k); cout

int my(int i); int main() { int k=3, m=0; m=my(k); cout

int my(int i); int main() { int k=3, m=0; m=my(k); cout

Передача аргументов в функцию по ссылке При передаче по ссылке в вызываемую функцию передаются ссылки на переменные – аргументы. Копии аргументов с именами формальных параметров не создаются. Вместо этого, по ссылке обеспечивается доступ к участкам памяти, занимаемым аргументами. Говоря другими словами, обработка аргументов ведется «на месте». Чтобы передать значения аргументов по ссылке, в качестве формальных параметров указывают переменные –ссылки. Все изменения формальных параметров, сделанные в функции, происходят с аргументами. Если в качестве аргумента по ссылке передается константа, то формальный параметр-ссылка должен быть объявлен с модификатором const. 4. Структурное программирование Функции

int my(int &i); int main() { int k=3, m=0; m=my(k); cout

int my(int &i); int main() { int k=3, m=0; m=my(k); cout

int my(int &i); int main() { int k=3, m=0; m=my(k); cout

int my(int &i); int main() { int k=3, m=0; m=my(k); cout

int my(int &i); int main() { int k=3, m=0; m=my(k); cout

int my(int &i); int main() { int k=3, m=0; m=my(k); cout

int my(int &i); int main() { int k=3, m=0; m=my(k); cout

int my(int &i); int main() { int k=3, m=0; m=my(k); cout

Передача массивов по ссылке Массивы передаются в функции по ссылке. При этом записывать перед формальным параметров знак ссылки & не следует: int example (short a[3]); При описании в качестве формального параметра одномерного массива, его размер указывать необязательно: int example(short a[ ]); При описании в качестве формального параметра многомерного массива, его размер по левому измерению указывать необязательно: int example(short y[ ][4][3]); 4. Структурное программирование Функции

void set(short [ ][3], int); int main() { short a[2][3]={0}; set(a,2); return 0; } void set (short k[ ][3], int m) { for (short i=0; i

void set(short [ ][3], int); int main() { short a[2][3]={0}; set(a,2); return 0; } void set (short k[ ][3], int m) { for (short i=0; i

void set(short [ ][3], int); int main() { short a[2][3]={0}; set(a,2); return 0; } void set (short k[ ][3], int m) { for (short i=0; i

void set(short [ ][3], int); int main() { short a[2][3]={0}; set(a,2); return 0; } void set (short k[ ][3], int m) { for (short i=0; i

void set(short [ ][3], int); int main() { short a[2][3]={0}; set(a,2); return 0; } void set (short k[ ][3], int m) { for (short i=0; i

Передача указателей в функции Указатели обычно передаются по значению. Доступ к объектам, на которые они указывают при этом происходит «на месте». Применение указателя в качестве параметра позволяет функции получить аргумент, а не его копию. 4. Структурное программирование Функции

int my(int *i); int main() { int k=3, m=0; m=my(&k); cout

F7A30 F5CF5EF60F62F64F66F68F7AF7AF7CF7CF7EF7EF80 k m &i АЛУ 4. Структурное программирование Функции int my(int *i); int main() { int k=3, m=0; m=my(&k); cout

2F7A30 F5CF5EF60F62F64F66F68F7AF7AF7CF7CF7EF7EF80 k m p АЛУ 4. Структурное программирование Функции int my(int *i); int main() { int k=3, m=0; m=my(&k); cout

2F7A30 F5CF5EF60F62F64F66F68F7AF7AF7CF7CF7EF7EF80 k m p АЛУ 3*2 = 6 4. Структурное программирование Функции int my(int *i); int main() { int k=3, m=0; m=my(&k); cout

2F7A60 F5CF5EF60F62F64F66F68F7AF7AF7CF7CF7EF7EF80 k m p АЛУ 3*2 = 6 4. Структурное программирование Функции int my(int *i); int main() { int k=3, m=0; m=my(&k); cout

2F7A60 F5CF5EF60F62F64F66F68F7AF7AF7CF7CF7EF7EF80 k m p АЛУ 2+6 = 4. Структурное программирование Функции int my(int *i); int main() { int k=3, m=0; m=my(&k); cout

82F7A60 F5CF5EF60F62F64F66F68F7AF7AF7CF7CF7EF7EF80 k m p АЛУ 2+6 = 8 4. Структурное программирование Функции my int my(int *i); int main() { int k=3, m=0; m=my(&k); cout

868 F5CF5EF60F62F64F66F68F7AF7AF7CF7CF7EF7EF80 k m АЛУ 4. Структурное программирование Функции my int my(int *i); int main() { int k=3, m=0; m=my(&k); cout

Передача указателей на функции Указатель может хранить адрес функции. Это позволяет присваивать ему адрес точки вызова функции и вызывать ее через указатель. Указатель на функцию должен не только содержать адрес памяти, где находится функция, которую необходимо вызвать. Такой указатель должен поддерживать информацию о количестве и типах аргументов и типе возвращаемого значения. Объявление указателей на функцию: Тип_возврата (* Имя_указателя ) ( список_типов_параметров ); Скобки, в которые взято *Имя_указателя позволяет отличит описание указателя на функцию double (*pfun)(char*, int); от описания прототипа функции, возвращающей указатель на double: double *pfun (char*, int); 4. Структурное программирование Функции

Передача указателей на функции: пример double calc_fun (double (*p_f)(double), double x); int main() { double (*p_func)(double)=NULL; p_func=sin; // можно и p_func = &sin; cout

Инициализация параметров Параметры функции, передаваемые по значению, можно инициализировать в ее прототипе Если при вызове функции аргумент, соответствующий инициализированному формальному параметру будет опущен, формальному параметру будет присвоено инициализирующее значение. Если аргумент при вызове задан, инициализирующее значение игнорируется. Инициализировать можно произвольное число параметров функции Так как аргументы сопоставляются формальным параметрам по порядку следования, то, чтобы опустить при вызове какой-либо аргумент придется опустить и все следующие за ним. 4. Структурное программирование Функции

Инициализация параметров void repchar (char с = _', int n = 20); int main () { repchar (); // ___________________ repchar (&'); // &&&&&&&&&&&&&&&& repchar ('=', 10); /// ========= _getch(); return 0; } void repchar (char с, int n) { for (int i=1; i

Перегрузка функций Перегруженная функция выполняет различные действия, зависящие от количества аргументов и типов данных, передаваемых ей в качестве аргументов Для того, чтобы создать перегруженную функцию необходимо описать требуемое число одноименных функций с требуемыми наборами формальных параметров. Сопоставив количество и типы аргументов при вызове, компилятор сгенерирует обращение к требуемой перегруженной функции. 4. Структурное программирование Функции

Перегрузка функций void repchar (); void repchar (char с); void repchar (int n); void repchar (char c, int n); int main () { repchar (); // ______________ repchar (5); // _____ repchar ('=', 3); // === repchar ('+'); // _getch(); return 0; } 4. Структурное программирование Функции void repchar () { for (int i=1; i

Возвращаемые значения В случае, если функция возвращает значение, его тип должен быть определен в описании функции. Он указывается перед идентификатором функции в описании прототипа и в заголовке функции. Количество аргументов у функции может быть произвольным, но возвращаемое значение только одно (или ни одного). Если функция не возвращает значения, в качестве типа возвращаемого значения следует указать void (по умолчанию считается, что функция возвращает целочисленное значение). Возвращаемое значение является операндом оператора return. В качестве возвращаемого значения может быть указано выражение, вырабатывающее значение соответствующего типа. 4. Структурное программирование Функции

Структуры как возвращаемые значения В С в качестве возвращаемых значений могут фигурировать структуры. struct myst { short i; short j; }; myst init (); int main() { myst r; r=init(); return 0; } 4. Структурное программирование Функции myst init() { myst w; w.i=1; w.j=2; return w; }

Массивы и структуры как возвращаемые значения Массив не может быть непосредственно возвращаемым значением. Зато вполне можно вот так: struct myst { short k [10]; }; myst init (int n); int main() { myst r; r=init(10); return 0; } 4. Структурное программирование Функции myst init(int n) { myst w; for (int i=0; i

Возврат ссылок: функция в левой части оператора присваивания Функция может возвращать ссылку на объект программы В этом случае записанное по адресу, на который указывает ссылка, значение может быть модифицировано. Для этого вызов функции должен осуществляться из левой части оператора присваивания. 4. Структурное программирование Функции

char &repl (int i, char c[ ]); int main() { char str[]="Hehlo"; repl(2,str)=l'; cout

char &repl (int i, char c[ ]); int main() { char str[]="Hehlo"; repl(2,str)=l'; cout

char &repl (int i, char c[]); int main() { char str[]="Hehlo"; repl(2,str)=l'; cout

char &repl (int i, char c[]); int main() { char str[]="Hehlo"; repl(2,str)=l'; cout

char &repl (int i, char c[]); int main() { char str[]="Hehlo"; repl(2,str)=l'; cout

Возврат ссылок: предупреждение Внимание: рассмотренный выше пример находится на грани фола. Возвращаемая ссылка остается действительной (ссылается на существующий после вызова функции объект ) только потому, что массив с – формальный параметр и ссылается на то же место в памяти, что и продолжающий существование массив str. Гораздо спокойнее возвращать ссылки на глобальные или статические переменные. Все сказанное относится и к возврату указателей. Пример некорректной функции: char &repl(int i) { char c=Hello; return c[i]; } 4. Структурное программирование Функции

Области видимости и классы памяти переменных Область видимости определяет, из каких частей программы возможен доступ к переменной Класс памяти определяет время, в течение которого перменная существует в памяти компьютера В С++ существуют 3 типа области видимости переменных: локальная область видимости область видимости файла область видимости класса (будет рассмотрена позднее) Переменные, имеющие локальную область видимости доступны только внутри того блока, в котором они определены (блоком обычно считается код, заключенный в фигурные скобки) Переменные, имеющие область видимости файла, доступны из любого места файла, в котором они определены 4. Структурное программирование Функции

Области видимости и классы памяти переменных В С++ существует 3 класса памяти: auto (автоматический) static (статический) динамический (будет рассмотрен позднее) Автоматическая переменная «рождается» в момент ее объявления и прекращает свое существование в момент завершения выполнения блока, где она определена. Автоматическая переменная не инициализируется автоматически. Если она инициализируется при объявлении, инициализация будет выполняться каждый раз при входе в блок и «рождении» переменной. У переменных, имеющих класс памяти static, время жизни равно времени жизни всей программы. Статическая переменная по умолчанию инициализируется нулем. Статическая переменная создается и инициализируется один раз – при первом выполнении блока. 4. Структурное программирование Функции

Локальные автоматические переменные int main() { int k=1; int i=10; cout

Локальные статические переменные int main() { static int k=1; for (int j=1; j

Области видимости и классы памяти переменных Глобальные переменные объявляются вне всех блоков и классов (о последних речь пойдет позже) и имеют область видимости файла. Они доступны всем функциям и блокам, начиная с той точки файла программы, где они объявлены. Глобальные переменные можно сделать доступными и из других файлов, если программа состоит из нескольких файлов. По умолчанию глобальные переменные имеют статический класс памяти. Глобальные переменные живут все время выполнения программы. Если они не инициализируются явно, по умолчанию, глобальные переменные инициализируются нулевым значением. По возможности, использования глобальных переменных следует избегать 4. Структурное программирование Функции

Просто пример: внутреннее представление переменных int internal_form (void *p, int n_bytes, char str [72]) // Explores memory area from p within n_bytes (n_bytes

Просто пример: внутреннее представление переменных for (int i=0; i=1) // bits in the byte { m = k; k >>= 1; k

Просто пример: внутреннее представление переменных int internal_form (void *p, int n_bytes, char str [72]); int main() // Example: how to get an internal form of a variable { typedef short my_type; //type to be explored my_type c=-2; // variable to be explored char str [72] = {0}; // this string will represent memory void *p = &c; if (!internal_form (p, sizeof (my_type), str)) cout

Преобразовать указатель void* p в указатель char* pc Входные параметры: указатель на область памяти void *p, число байт n_bytes Выходной параметр: строка char str [72] [n_bytes>8] return-1 [n_bytes>=1; k=1 (отбрасываем обработанный бит) i++; pc++ (сдвигаемся на 1 байт) [j 7] Диаграмма деятельности для функции анализа внутреннего представления переменных Аварийное завершение Нормальное заверешение [m == k][m != k] Пока не переберем все анализируемые байты Пока не проанализируем все биты исследуемого байта Индекс с учетом расстояния (пробела) между байтами в строке str Если после битового сдвига вправо - сдвига влево число не изменилось, крайний правый бит - 0, иначе - 1

Еще один пример: решение нелинейного уравнения x=f(x) методом простых итераций Постановка задачи Методом последовательных приближений найти решение уравнения x=f(x) с заданной точностью r. Математическая модель. Выберем начальное приближение x 0 Положим x 1 =f(x 0 ); x 2 =f(x 1 ); … x n =f(x n -1) Погрешность d = |x n-1 -f(x n-1 )| = |x n-1 -x n | Условие сходимости: |f'(x)|

Еще один пример: решение нелинейного уравнения x=f(x) методом простых итераций Данные. Заданная точность float r Текущая погрешность float d Текущее значение x n-1 float x Текущее значение f(x n-1 ) float y Алгоритм. 1.Задать x=x 0, r 2.Если r < 1e-6, положить r = 1e-6 3. Инициализировать d=2*r 4. Пока d>r выполнять 4.1. Вычислить y = cos(x) 4.2. Положить d = |x-y| 4.3. Положить x = y 5. Вывести значение x 4. Структурное программирование Функции Полученный ранее алгоритм на псевдокоде

Еще один пример: решение нелинейного уравнения x=f(x) методом простых итераций Параметры: Заданная точность double r Начальное приближение double x Указатель на функцию double (*p_func)(double); Максимальное число итераций integer max_i Достигнутая точность double &d Возвращаемое значение: Решение double x Внутренние переменные: Текущее значение x n-1 double x Текущее значение f(x n-1 ) double y Алгоритм. 1. Если r < 1e-12, положить r = 1e Инициализировать d=2*r, y=0 4. Пока d>r и число итераций не больше максимального и y

Еще один пример: решение нелинейного уравнения x=f(x) методом простых итераций double solveqn (double r, double x, double (*p_func)(double), int max_i, double&d) // Solves equation f(x)=0 // r - required precision (

Еще один пример: решение нелинейного уравнения x=f(x) методом простых итераций double solveqn (double r, double x, double (*p_func)(double), int max_i, double&d); double myfun(double x); int main() // Example: how to solve an equation f(x)=0 { double d = 0; cout

4. Структурное программирование Рекурсия Рекурсивным называется объект, который частично определяется через самого себя. (1)0!=1 (2)для любых n>0 n! = n*(n-1)! int fact (int i); int main() { cout

4. Структурное программирование Рекурсия Нерекурсивное определение факториала n!=1*2*3*…*n int fact (int i); int main() { cout

Содержание и мощность рекурсивного определения, а также его главное назначение, состоит в том, что оно позволяет с помощью конечного выражения определить бесконечное множество объектов. Аналогично, с помощью конечного рекурсивного алгоритма можно определить бесконечное вычисление, причем алгоритм не будет содержать повторений фрагментов текста. Для создания рекурсивных алгоритмов необходимо и достаточно наличие понятия функции (и разрешения рекурсивных вызовов). Это вытекает из того, что функции позволяют дать любой последовательности действий (операторов) имя, с помощью которого можно будет эту последовательность действий вызывать. 4. Структурное программирование Рекурсия

В общем случае любая рекурсивная процедура Rec включает в себя некоторое множество операторов S и один или несколько операторов рекурсивного вызова Р. Вызов рекурсивной процедуры должен выполняться по условию, которое на каком-то уровне рекурсии станет ложным. Если условие истинно, то цепочка рекурсивных вызовов продолжается. Когда оно становится ложным, то рекурсивный спуск заканчивается и начинается поочередный рекурсивный возврат из всех вызванных на данный момент копий рекурсивной процедуры. 4. Структурное программирование Рекурсия

Максимальное число рекурсивных вызовов процедуры без возвратов, которое происходит во время выполнения программы, называется глубиной рекурсии. Число рекурсивных вызовов в каждый конкретный момент времени, называется текущим уровнем рекурсии. 4. Структурное программирование Рекурсия

Структура рекурсивной процедуры может принимать три разных формы: 1.Форма с выполнением действий до рекурсивного вызова (с выполнением действий на рекурсивном спуске). void Rec() { … S … ; if (условие) Rec (); return; } 4. Структурное программирование Рекурсия

Вычисление факториала на рекурсивном спуске: unsigned int fact_dn (int m, unsigned int worker=1); int main () { cout

Трассировка вызовов 1) cout

4. Структурное программирование Рекурсия (1) m=3, worker=4; fact_dn=? Трассировка вызовов 1) cout

4. Структурное программирование Рекурсия (1) m=4, worker=4; fact_dn=? Трассировка вызовов 1)cout

4. Структурное программирование Рекурсия (1) m=4, worker=4; fact_dn=? Трассировка вызовов 1)cout

4. Структурное программирование Рекурсия (1) m=4, worker=4; fact_dn=? Трассировка вызовов 1)cout

4. Структурное программирование Рекурсия (1) m=4, worker=4; fact_dn=? Трассировка вызовов 1)cout

4. Структурное программирование Рекурсия (1) m=4, worker=4; fact_dn=? (2) m=3, worker=12; fact_dn=? (3) m=2, worker=24; fact_dn=? (4) m=1, worker=24; fact_dn=? int fact_dn (int m, int worker) { worker *= m; if (m!= 1) return fact_dn (m-1, worker); else return worker; } Трассировка вызовов 1)cout

4. Структурное программирование Рекурсия (1) m=4, worker=4; fact_dn=? (2) m=3, worker=12; fact_dn=? (3) m=2, worker=24; fact_dn=? (4) m=1, worker=24; fact_dn=? int fact_dn (int m, int worker) { worker *= m; if (m!= 1) return fact_dn (m-1, worker); else return worker; } Трассировка вызовов 1)cout

4. Структурное программирование Рекурсия int fact_dn (int m, int worker) { worker *= m; if (m!= 1) return fact_dn (m-1, worker); else return worker; } (1) m=4, worker=4; fact_dn=? (2) m=3, worker=12; fact_dn=? (3) m=2, worker=24; fact_dn=? (4) m=1, worker=24; fact_dn=24 Трассировка вызовов 1)cout

4. Структурное программирование Рекурсия int fact_dn (int m, int worker) { worker *= m; if (m!= 1) return fact_dn (m-1, worker); else return worker; } (1) m=4, worker=4; fact_dn=? (2) m=3, worker=12; fact_dn=? (3) m=2, worker=24; fact_dn=24 Трассировка вызовов 1)cout

Трассировка вызовов 1)cout

Трассировка вызовов 1)cout

Вычисление факториала на рекурсивном спуске: int fact_dn (int m, int worker=1); int main () { cout

Вычисление факториала на рекурсивном спуске: unsigned long fact_dn (unsigned int m, unsigned long worker=1); int main () { cout

Структура рекурсивной процедуры может принимать три разных формы: 2.Форма с выполнением действий после рекурсивного вызова (с выполнением действий на рекурсивном возврате). void Rec() { if условие Rec (); … S … ; return; } 4. Структурное программирование Рекурсия

Вычисление факториала на рекурсивном возврате: int fact_up (int m); int main () { cout

Трассировка вызовов 1)cout

4. Структурное программирование Рекурсия Трассировка вызовов 1)cout 1) return m * fact_up (m - 1); else return 1; } (2) m=3, fact_up=?

4. Структурное программирование Рекурсия Трассировка вызовов 1)cout 1) return m * fact_up (2); (1) m=4, fact_up=? unsigned long fact_up (unsigned int m) { if (m > 1) return m * fact_up (m - 1); else return 1; } (2) m=3, fact_up=? (3) m=2, fact_up=?

4. Структурное программирование Рекурсия Трассировка вызовов 1)cout 1) return m * fact_up (2); 4)if (2 > 1) return m * fact_up (1); (1) m=4, fact_up=? unsigned long fact_up (unsigned int m) { if (m > 1) return m * fact_up (m - 1); else return 1; } (2) m=3, fact_up=? (3) m=2, fact_up=? (4) m=1, fact_up=?

4. Структурное программирование Рекурсия Трассировка вызовов 1)cout 1) return m * fact_up (2); 4)if (2 > 1) return m * fact_up (1); (1) m=4, fact_up=? unsigned long fact_up (unsigned int m) { if (m > 1) return m * fact_up (m - 1); else return 1; } (2) m=3, fact_up=? (3) m=2, fact_up=? (4) m=1, fact_up=1

4. Структурное программирование Рекурсия Трассировка вызовов 1)cout 1) return m * fact_up (2); (1) m=4, fact_up=? unsigned long fact_up (unsigned int m) { if (m > 1) return m * fact_up (m - 1); else return 1; } (2) m=3, fact_up=? (3) m=2, fact_up=2*1

4. Структурное программирование Рекурсия Трассировка вызовов 1)cout 1) return m * fact_up (m - 1); else return 1; } (2) m=3, fact_up=3*2

4. Структурное программирование Рекурсия Трассировка вызовов 1)cout

Вычисление факториала на рекурсивном возврате: int fact_up (int m); int main () { cout

Вычисление факториала на рекурсивном возврате: int fact_up (int m); int main () { cout

Структура рекурсивной процедуры может принимать три разных формы: 3.Форма с выполнением действий как до, так и после рекурсивного вызова (с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате). void Rec () { … S1 …; if (условие) Rec(); … S2 … ; return; }; void Rec () { if (условие) { … S1 …; Rec; … S2 … ; } return; } 4. Структурное программирование Рекурсия

Инвертирование строки void reverse(); int main() { reverse(); cout

Инвертирование строки void reverse(); int main() { reverse(); cout

Инвертирование строки void reverse(); int main() { reverse(); cout

Инвертирование строки void reverse(); int main() { reverse(); cout

Инвертирование строки void reverse(); int main() { reverse(); cout

Инвертирование строки void reverse(); int main() { reverse(); cout

Инвертирование строки void reverse(); int main() { reverse(); cout

Инвертирование строки void reverse(); int main() { reverse(); cout

Инвертирование строки void reverse(); int main() { reverse(); cout

Инвертирование строки void reverse(); int main() { reverse(); cout

Инвертирование строки void reverse(); int main() { reverse(); cout

Инвертирование строки void reverse(); int main() { reverse(); cout

Инвертирование строки void reverse(); int main() { reverse(); cout

Инвертирование строки void reverse(); int main() { reverse(); cout

Инвертирование строки void reverse(); int main() { reverse(); cout

Инвертирование строки void reverse(); int main() { reverse(); cout

Подадим на вход строку HELLO: Текущий уровень рекурсии Рекурсивный спуск Рекурсивный возврат 0Reverse; 1 с != 13; Ввод:c=H'; Reverse;Вывод:'Н'; 2 c != 13; Ввод:c='Е'; Reverse;Вывод:E'; 3 c != 13; Ввод:c=L'; Reverse;Вывод:'L'; 4 c != 13; Ввод:c=L'; Reverse;Вывод:L'; 5 c != 13; Ввод:c=O'; Reverse;Вывод:O'; 6 c = 13; Нажатие 4. Структурное программирование Рекурсия

Быстрая сортировка Qsort(1,5) Qsort(6,10) Qsort(1,10) j=2, i=4 j=9, i=10=R Qsort(1,2)Qsort(4,5) Qsort(6,9)Вызов не выполняется Qsort(8,9) B=7 B=4 B=12 j=1=L, i=2=R j=3

Быстрая сортировка Сортируем массив, содержащий информацию о деталях: struct detail { int id; float weight; }; Спецификация функции быстрой сортировки: void qsort (detail s [ ], int l, int r); 4. Структурное программирование Рекурсия

struct detail { int id; float weight; }; void qsort (detail s [ ], int l, int r); int main() { const int n=9; detail st [n+1]; srand( static_cast (time(NULL))); for (int i=0; i

void qsort (detail s[ ], int l, int r) { int b=0, i=0, j=0; detail tmp; b = s[(l+r)/2].id; i = l; j = r; while (i b) j--; if (i

struct Member { int id; Name ownname; Date birth; char address [80]; Date enter; char position [30]; bool tradeunion; }; 4. Структурное программирование Шаблоны функций struct detail { int id; float weight; }; Быстрая сортировка: шаблоны функций template void qsort (T s [ ], int l, int r); struct Date { unsigned short year; unsigned short month; unsigned short day; }; struct Name { char surname [80]; char firstname [40]; char patronymic [60]; };

Быстрая сортировка: шаблоны функций int main() { const int n=12; detail st[n+1]; srand( static_cast (time(NULL))); for (int i=0; i

template void qsort (T s [ ], int l, int r) { int b=0, i=0, j=0, k=0; T tmp; b = s[(l+r)/2].key; i = l; j = r; while (i b) j--; if (i

Шаблоны функций Заголовку тела функции также должна предшествовать конструкция template. Шаблонная функция может быть перегружена другим шаблоном или не шаблонной функцией с таким же именем, но с другим набором параметров. Еще один простой пример шаблона – функция, осуществляющая перестановку элементов произвольного типа: template void myswap (T *a, T *b) { T tmp=*a; *a=*b; *b=tmp; } 4. Структурное программирование Шаблоны функций

Шаблоны функций Еще один простой пример шаблона – функция, осуществляющая перестановку элементов произвольного типа: template void myswap (T *a, T *b) { T tmp=*a; *a=*b; *b=tmp; } int main() { int short x=15, y=2; double a=0, b=12.4; myswap (&x,&y); myswap (&a,&b); return 0; } 4. Структурное программирование Шаблоны функций

Шаблоны функций То же самое лучше можно сделать с помощью ссылок, а не указателей: template void myswap (T &a, T &b) { T tmp= a; a=b; b=tmp; } int main() { int short x=15, y=2; double a=0, b=12.4; myswap (x,y); myswap (a,b); return 0; } 4. Структурное программирование Шаблоны функций