Void swap(int a, int b)

{

int temp; // temp – локальная переменная

temp=a; // алгоритм циклического обмена

a=b;

b=temp;

}

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

void swap(int *a, int *b) // используем значения переменных

{ // по адресам переменных a и b

Int temp;

temp=*a; // алгоритм циклического обмена

*a=*b; // значениями, находящимися

*b=temp; // по этим адресам

}

Эта функция использует не формальные параметры, а значения, находящиеся по адресам формальных параметров. Сами адреса переменных функцией не изменяются, как это и положено формальным параметрам. Меняются только значения, находящиеся по данным адресам, а эти значения не являютсяформальными параметрами. Хитро придумано!

Обратимся к этой функции, например, из головной программы:

int x, y;

x = 5;

y = 3;

swap(&x, &y); // используем адреса фактических переменных

В этом случае переменные xиy обменяются своими значениями.

Если в качестве формальных параметров используются имена массивов(строк), то в списке формальных параметров перед ними знаки амперсанда &не ставятся: имя массива вСиявляетсяадресом его первого элемента. Поэтому в функцию передается не массив со всеми значениями его элементов, а только адрес его первого элемента. Адреса всех остальных элементов вычисляютсяавтоматически:

Void poplavok(int n, int vector[n])

{

int top, bottom, temp;

for (top=0, bottom = n-1; top<bottom; top++, bottom--)

{

temp = vector[top];

vector[top] = vector[bottom];

vector[bottom] = temp;

}

}

Эта функция переворачивает вектор vector[n]– выполняет «поплавок».

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

void poplavok(int n, int vector[])

Обратимся к этой функции из головной программы:

#include <stdio.h>

#include <conio.h>

void poplavok(int n, int vector[]); // прототип функции

int main()

{

int i, k=5;

int vect[k] = {1,2,3,4,5}; // инициализация вектора

printf("\n"); // вывод исходного вектора

for (i=0; i<k; i++)

printf("%5d", vect[i]);

printf("\n");

poplavok(k, vect); // обращение к функции

for (i=0; i<k; i++) // вывод полученного вектора

printf("%5d", vect[i]);

printf("\n");

printf("\n");

}

void poplavok(int n, int vector[]) // описание функции

{

int top, bottom, temp;

for (top=0, bottom = n-1; top<bottom; top++, bottom--)

{

temp = vector[top];

vector[top] = vector[bottom];

vector[bottom] = temp;

}

}

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

1 2 3 4 5

5 4 3 2 1

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

void vorm_mass(int n, int m, int mass[n][m])

{

int i, j;

for (i=0; i<n; i++)

for (j=0; j<m; j++)

{

mass[i][j]=i + j;

}

}

Обратимся к этой функции из головной программы:

#include <stdio.h>

#include <conio.h>

void vorm_mass(int n, int m, int mass[n][m]); // прототип

int main()

{

int i, j;

int k=2, d=3;

int massiv[k][d];

vorm_mass(k, d, massiv); // обращение к функции

printf("\n");

for (i=0; i<k; i++) // вывод полученного массива

{ // построчно

for (j=0; j<d; j++)

printf("%5d", massiv[i][j]);

printf("\n");

}

}

void vorm_mass(int n, int m, int mass[n][m])

{ // описание функции

int i, j;

for (i=0; i<n; i++)

for (j=0; j<m; j++)

{

mass[i][j]=i + j;

}

}

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

0 1 2

1 2 3

Рекурсия

Использование рекурсии в программировании базируется на рекурсивных математических определениях. Считается, что в математике рекурсивность как принцип определений используется с 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,

F_n= 1 при n = 2,

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

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

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

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

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

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

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

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

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

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

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

long factorial(int n)

{

if (n <= 1)

return 1; // выход из рекурсии – терминальная ветвь

else return n * factorial(n-1);

}

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

factorial := 5 * factorial(4)