Таким образом, функции, используемые в программе, должны быть обязательно объявлены – указан их прототип. Прототип – это заголовок функции с указанием ее типа, имени, типов и имен аргументов – формальных параметров:
void vorm_mass(int n, int m, int mass[n][m]);
Внимание! После закрывающих скобок точка с запятой ставится обязательно!
Таким образом, прототип функции полностью соответствует ее заголовку, используемому при ее дальнейшем описании.
Сами функции описываются после головной программы:
{
int s; // s – локальная переменная
s = a + b;
return s; // возврат вычисленного значения
}
void vorm_mass(int n, int m, int mass[n][m])
{
for (i=0; i<n; i++)
for (j=0; j<m; j++)
{
// задание значений элементам массива mass[n][m]
}
}
Внимание! После заголовка функции и закрывающих фигурных скобок точка с запятой не ставится!
В последнем случае оператор return не нужен, так как функция vorm_mass имеет тип void – ничего не возвращает.
Если функция не имеет формальных параметров, то их в заголовке функции не указывают, но круглые скобки оставляют.
Необходимо отметить, что описания констант, типов данных и переменных, стоящих внутри фигурных скобок функции, являются локальными, то есть они действуют только в пределах данной функции.
Взаимное расположение функций в программе может быть произвольным. Однако следует избегать обращения к функции, еще не объявленной или не описанной, так как такая функция для компилятора всегда будет иметь тип int.
После заголовка функции записывается тело функции - последовательность локальных описаний и операторов в соответствии с алгоритмом ее работы.
Функция возвращает вычисленное значение, если она заканчивается оператором возврата return, после которого следует имя переменной или выражение, значение которого должна определить функция:
{
return a + b; // возврат вычисленного значения
}
Если после слова return ничего не стоит или этого слова вообще нет в функции, то значит, что данная функция не возвращает никакого значения, и поэтому в ее заголовке должен быть указан тип void.
Формальные параметры функции в Си соответствуют параметрам-значениям подпрограмм в Паскале: они служат только для передачи значений фактических параметров в функцию и вычисления ее значения. Поэтому даже если внутри функции они изменяются, то соответствующие им фактические (входные) параметры не изменяются, оставаясь такими же, какими они были при вызове функции: с чем пришел – с тем и ушел:
{
int s; // s – локальная переменная
a++;
b++;
s = a + b;
return s; // возврат вычисленного значения
}
Внутри тела функции формальные параметры a и b увеличились на единицу, и сумма определяется при их новых значениях. При выходе из этой функции фактические (входные) параметры, соответствующие этим формальным параметрам, не изменятся.
Таким образом, функция в Си вычисляет единственное значение, передаваемое вовне оператором return .
При необходимости определить одной функцией значения нескольких переменных, в списке формальных параметров включаются не имена этих переменных, а их адреса (ссылки), а в теле функции используется операция разадресации (обращения по адресу) * .
Создадим функцию, которая обменивает значениями две переменных:
{
int temp; // temp – локальная переменная
temp=a; // алгоритм циклического обмена
a=b;
b=temp;
}
Эта функция не производит никаких действий над фактическими параметрами, так как будут обмениваться значениями только формальные параметры: с чем пришел – с тем и ушел. Перепишем ее следующим образом:
void swap(int *a, int *b) // используем значения переменных
{ // по адресам переменных a и b
temp=*a; // алгоритм циклического обмена
*a=*b; // значениями, находящимися
*b=temp; // по этим адресам
}
Эта функция использует не формальные параметры, а значения, находящиеся по адресам формальных параметров. Сами адреса переменных функцией не изменяются, как это и положено формальным параметрам. Меняются только значения, находящиеся по данным адресам, а эти значения не являются формальными параметрами. Хитро придумано!
Обратимся к этой функции, например, из головной программы:
В этом случае переменные x и y обменяются своими значениями.
Если в качестве формальных параметров используются имена массивов (строк), то в списке формальных параметров перед ними знаки амперсанда &не ставятся: имя массива в Си является адресом его первого элемента. Поэтому в функцию передается не массив со всеми значениями его элементов, а только адрес его первого элемента. Адреса всех остальных элементов вычисляются автоматически:
void poplavok(int n, int vector[n])
{
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 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[]) // описание функции
{
for (top=0, bottom = n-1; top<bottom; top++, bottom--)
{
temp = vector[top];
vector[top] = vector[bottom];
vector[bottom] = temp;
}
}
На экран будет выведено:
Если в качестве формального параметра функции используется многомерный массив, то в заголовке функции после его имени в отдельных квадратных скобках указываются все его размеры:
void vorm_mass(int n, int m, int mass[n][m])
{
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 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])
{ // описание функции
for (i=0; i<n; i++)
for (j=0; j<m; j++)
{
mass[i][j]=i + j;
}
}
Результат работы программы:
Использование рекурсии в программировании базируется на рекурсивных математических определениях. Считается, что в математике рекурсивность как принцип определений используется с 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 байт. Поэтому последовательность рекурсивных обращений не может быть бесконечной. В любой рекурсивной подпрограмме должна быть нерекурсивная (терминальная) ветвь, обеспечивающая выход из рекурсии. При переполнении стека работа программы прерывается, и появляется сообщение об ошибке.
Рекурсивная функция, вычисляющая факториал заданного числа n, может иметь вид:
Например, вычисление факториала целого неотрицательного числа n! = 1·2·3·…·(n-1) · n . Кроме того, по определению, 0! = 1. Рекурсивное математическое определение факториала имеет вид:
В ней два первых числа фиксированы и равны единице, а каждое последующее число равно сумме двух предыдущих. Рекурсивное математическое определение числа Фибоначчи с порядковым номером n имеет вид: