Шпаргалка по языку СИ. Конспект Лекций «программирование На Языке Высокого Уровня Си» П. Конспект лекций для студентов высших учебных заведений, обучающихся по специальности 230102. 65 Автоматизированные системы обработки информации и управления

• Название: Конспект лекций для студентов высших учебных заведений, обучающихся по специальности 230102. 65 Автоматизированные системы обработки информации и управления
• Анкор: Шпаргалка по языку СИ
• Дата: 26.05.2022
• Размер: 1.25 Mb.
• Имя файла: Конспект Лекций «программирование На Языке Высокого Уровня Си» П.pdf
• Тип: Конспект лекций; #550544
• страница: 6 из 15

Тема 8. Функции
В отличие от других языков программирования высокого уровня в языке
СИ нет деления на процедуры, подпрограммы и функции, здесь вся программа строится только из функций.
Определение функций в языке Си
Функция
−
это совокупность объявлений и операторов, обычно предназначенная для решения определенной задачи. Каждая функция должна иметь имя, которое используется для ее объявления, определения и вызова. В любой программе на СИ должна быть функция с именем main (главная функция), именно с этой функции, в каком бы месте программы она не находилась, начинается выполнение программы.
При вызове функции ей при помощи аргументов (формальных параметров) могут быть переданы некоторые значения (фактические параметры), используемые во время выполнения функции. Функция может возвращать только одно значение. Это возвращаемое значение и есть результат выполнения функции, который при выполнении программы подставляется в точку вызова функции, где бы этот вызов ни встретился. Допускается также использовать
107

функции, не имеющие аргументов, и функции, не возвращающие никаких значений. Действие таких функций может состоять, например, в изменении значений некоторых переменных, выводе на печать некоторых текстов и т.п.
С использованием функций в языке СИ связаны три понятия - определение функции (описание действий, выполняемых функцией), объявление функции
(задание формы обращения к функции) и вызов функции.
Определение функции задает тип возвращаемого значения, имя функции, типы и число формальных параметров, а также объявления переменных и операторы, называемые телом функции, и определяющие действие функции. В определении функции также может быть задан класс памяти.
В данном примере определена функция с именем rus, имеющая один параметр с именем r и типом unsigned char. Функция возвращает целое значение, равное 1, если параметр функции является буквой русского алфавита, или 0 в противном случае.
int rus (unsigned char r)
{
if (r>='А' && c<=' ')
return 1;
else
return 0;
}
В языке СИ нет требования, чтобы определение функции обязательно предшествовало ее вызову. Определения используемых функций могут следовать за определением функции main, перед ним, или находится в другом файле.
Однако для того, чтобы компилятор мог осуществить проверку соответствия типов передаваемых фактических параметров типам формальных параметров до вызова функции нужно поместить объявление (прототип) функции.
Объявление функции имеет такой же вид, что и определение функции, с той лишь разницей, что тело функции отсутствует, и имена формальных параметров тоже могут быть опущены. Для функции, определенной в последнем примере, прототип может иметь вид
108

int rus (unsigned char r); или rus (unsigned char);
В программах на языке Си широко используются, так называемые, библиотечные функции, т.е. функции, предварительно разработанные и записанные в библиотеки. Прототипы библиотечных функций находятся в специальных заголовочных файлах, поставляемых вместе с библиотеками в составе систем программирования, и включаются в программу с помощью директивы #include. Состав основных библиотек языка Си представлено в
Приложении 1.
Если объявление функции не задано, то по умолчанию строится прототип функции на основе анализа первой ссылки на функцию, будь то вызов функции или определение. Однако такой прототип не всегда согласуется с последующим определением или вызовом функции. Рекомендуется всегда задавать прототип функции. Это позволит компилятору либо выдавать диагностические сообщения, при неправильном использовании функции, либо корректным образом регулировать несоответствие аргументов, устанавливаемое при выполнении программы.
В соответствии с синтаксисом языка Си определение функции имеет следующую форму:
[<спецификатор класса памяти>] [<спецификатор типа>] <имя функции>
([<список формальных параметров>])
{<тело функции>}
Необязательный спецификатор класса памяти задает класс памяти функции, который может быть static или extern. Подробно классы памяти будут рассмотрены в следующем разделе.
Спецификатор типа функции задает тип возвращаемого значения и может задавать любой тип. Если спецификатор типа не задан, то предполагается, что функция возвращает значение типа int.
Функция не может возвращать массив или функцию, но может возвращать указатель на любой тип, в том числе и на массив и на функцию. Тип
109

возвращаемого значения, задаваемый в определении функции, должен соответствовать типу в объявлении этой функции.
Функция возвращает значение, если ее выполнение заканчивается оператором return, содержащим некоторое выражение. Указанное выражение вычисляется, преобразуется, если необходимо, к типу возвращаемого значения и возвращается в точку вызова функции в качестве результата. Если оператор return не содержит выражения или выполнение функции завершается после выполнения последнего ее оператора (без выполнения оператора return), то возвращаемое значение не определено. Для функций, не использующих возвращаемое значение, должен быть использован тип void, указывающий на отсутствие возвращаемого значения. Если функция определена как функция, возвращающая некоторое значение, а в операторе return при выходе из нее отсутствует выражение, то поведение вызывающей функции после передачи ей управления может быть непредсказуемым.
Список формальных параметров - это последовательность объявлений формальных параметров, разделенная запятыми. Формальные параметры
−
это переменные, используемые внутри тела функции и получающие значение при вызове функции путем копирования в них значений соответствующих фактических параметров. Список формальных параметров может заканчиваться запятой (,) или запятой с многоточием (,...), это означает, что число аргументов функции переменно. Однако предполагается, что функция имеет, по крайней мере, столько обязательных аргументов, сколько формальных параметров задано перед последней запятой в списке параметров. Такой функции может быть передано большее число аргументов, но над дополнительными аргументами не проводится контроль типов.
Если функция не использует параметров, то наличие круглых скобок обязательно, а вместо списка параметров рекомендуется указать слово void.
Порядок и типы формальных параметров должны быть одинаковыми в определении функции и во всех ее объявлениях. Типы фактических параметров при вызове функции должны быть совместимы с типами соответствующих
110

формальных параметров. Тип формального параметра может быть любым основным типом, структурой, объединением, перечислением, указателем или массивом. Если тип формального параметра не указан, то этому параметру присваивается тип int.
Для формального параметра можно задавать класс памяти register, при этом для величин типа int спецификатор типа можно опустить.
Идентификаторы формальных параметров используются в теле функции в качестве ссылок на переданные значения. Эти идентификаторы не могут быть переопределены в блоке, образующем тело функции, но могут быть переопределены во внутреннем блоке внутри тела функции.
При передаче параметров в функцию, если необходимо, выполняются обычные арифметические преобразования для каждого формального параметра и каждого фактического параметра независимо. После преобразования формальный параметр не может быть короче, чем int, т.е. объявление формального параметра с типом char равносильно его объявлению с типом int. А параметры, представляющие собой действительные числа, имеют тип double.
Преобразованный тип каждого формального параметра определяет, как интерпретируются аргументы, помещаемые при вызове функции в стек.
Несоответствие типов фактических аргументов и формальных параметров может быть причиной неверной интерпретации.
Тело функции это составной оператор, содержащий операторы,
˗
определяющие действие функции.
Все переменные, объявленные в теле функции без указания класса памяти, имеют класс памяти auto, т.е. они являются локальными. При вызове функции локальным переменным отводится память в стеке и производится их инициализация. Управление передается первому оператору тела функции и начинается выполнение функции, которое продолжается до тех пор, пока не встретится оператор return или последний оператор тела функции. Управление при этом возвращается в точку, следующую за точкой вызова, а локальные переменные становятся недоступными. При новом вызове функции для
111

локальных переменных память распределяется вновь, и поэтому старые значения локальных переменных теряются.
Параметры функции передаются по значению и могут рассматриваться как локальные переменные, для которых выделяется память при вызове функции и производится инициализация значениями фактических параметров. При выходе из функции значения этих переменных теряются. Поскольку передача параметров происходит по значению, в теле функции нельзя изменить значения переменных в вызывающей функции, являющихся фактическими параметрами.
Однако если в качестве параметра передать указатель на некоторую переменную, то используя операцию разадресации можно изменить значение этой переменной.
/*Неправильное использование параметров*/
void change (int x, int y)
{
int k=x;
x=y;
y=k;
}
/*Правильное использование параметров*/
void change (int *x, int *y)
{
int k=*x;
*x=*y;
*y=k;
}
При вызове такой функции в качестве фактических параметров должны быть использованы не значения переменных, а их адреса
change (&a,&b);
Если требуется вызвать функцию до ее определения в рассматриваемом файле, или определение функции находится в другом исходном файле, то вызов функции следует предварять объявлением этой функции. Объявление (прототип) функции имеет следующий формат:
[<спецификатор класса памяти>] [<спецификатор типа>] <имя функции>
([<список формальных параметров>]) [,<список имен функций>];
В отличие от определения функции, в прототипе за заголовком сразу же следует точка с запятой, а тело функции отсутствует. Если несколько разных функций возвращают значения одинакового типа и имеют одинаковые списки
112

формальных параметров, то эти функции можно объявить в одном прототипе, указав имя одной из функций в качестве имени функции, а все другие поместить в список имен функций, причем каждая функция должна сопровождаться списком формальных параметров. Правила использования остальных элементов формата такие же, как при определении функции. Имена формальных параметров при объявлении функции можно не указывать, а если они указаны, то их область действия распространяется только до конца объявления.
Прототип - это явное объявление функции, которое предшествует определению функции. Тип возвращаемого значения при объявлении функции должен соответствовать типу возвращаемого значения в определении функции.
Если прототип функции не задан, а встретился вызов функции, то строится неявный прототип из анализа формы вызова функции. Тип возвращаемого значения создаваемого прототипа int, а список типов и числа параметров функции формируется на основании типов и числа фактических параметров, используемых при данном вызове.
Таким образом, прототип функции необходимо задавать в следующих случаях:
1.
Функция возвращает значение типа, отличного от int;
2.
Требуется проинициализировать некоторый указатель на функцию до того, как эта функция будет определена.
Наличие в прототипе полного списка типов аргументов параметров позволяет выполнить проверку соответствия типов фактических параметров при вызове функции типам формальных параметров, и, если необходимо, выполнить соответствующие преобразования.
В прототипе можно указать, что число параметров функции переменно, или что функция не имеет параметров.
Если прототип задан с классом памяти static, то и определение функции должно иметь класс памяти static. Если спецификатор класса памяти не указан, то подразумевается класс памяти extern.
113

Вызов функций в языке Си
Вызов функции имеет следующий формат:
<Адресное выражение> ([<список выражений>])
Поскольку синтаксически имя функции является адресом начала тела функции, в качестве обращения к функции может быть использовано адресное- выражение (в том числе и имя функции или разадресация указателя на функцию), имеющее значение адреса функции.
Список выражений представляет собой список фактических параметров, передаваемых в функцию. Этот список может быть и пустым, но наличие круглых скобок обязательно.
Фактический параметр может быть величиной любого основного типа, структурой, объединением, перечислением или указателем на объект любого типа. Массив и функция не могут быть использованы в качестве фактических параметров, но можно использовать указатели на эти объекты.
Выполнение вызова функции происходит следующим образом:
1. Вычисляются выражения в списке выражений и подвергаются обычным арифметическим преобразованиям. Затем, если известен прототип функции, тип полученного фактического аргумента сравнивается с типом соответствующего формального параметра. Если они не совпадают, то либо производится преобразование типов, либо формируется сообщение об ошибке. Число выражений в списке выражений должно совпадать с числом формальных параметров, если только функция не имеет переменного числа параметров. В последнем случае проверке подлежат только обязательные параметры. Если в прототипе функции указано, что ей не требуются параметры, а при вызове они указаны, формируется сообщение об ошибке.
2. Происходит присваивание значений фактических параметров соответствующим формальным параметрам.
3. Управление передается на первый оператор функции.
4. Выполнение оператора return в теле функции возвращает управление и возможно, значение в вызывающую функцию. При отсутствии оператора return
114

управление возвращается после выполнения последнего оператора тела функции, а возвращаемое значение не определено.
Адресное выражение, стоящее перед скобками определяет адрес вызываемой функции. Это значит, что функция может быть вызвана через указатель на функцию.
int (*fun)(int x, int *y);
Здесь объявлена переменная fun как указатель на функцию с двумя параметрами: типа int и указателем на int. Сама функция должна возвращать значение типа int. Круглые скобки, содержащие имя указателя fun и признак указателя *, обязательны, иначе следующая запись будет интерпретироваться как объявление функции fun возвращающей указатель на int.
int *fun (intx,int *y);
Вызов функции возможен только после инициализации значения указателя fun и имеет вид:
(*fun)(i,&j);
В этом выражении для получения адреса функции, на которую ссылается указатель fun, используется операция разадресации *.
Указатель на функцию может быть передан в качестве параметра функции.
При этом разадресация происходит во время вызова функции, на которую ссылается указатель на функцию. Присвоить значение указателю на функцию можно в операторе присваивания, употребив имя функции без списка параметров.
double (*fun1)(int x, int y);
double fun2(int k, int l);
fun1 = fun2;
/* инициализация указателя на функцию */
(*fun1)(2,7);
/* обращение к функции */
Указатель на функцию fun1 описан как указатель на функцию с двумя параметрами, возвращающую значение типа double, и также описана функция fun2. В противном случае, т.е. когда указателю на функцию присваивается функция, описанная иначе, чем указатель, произойдет ошибка.
Пример 27. Разработать функцию, вычисляющую производную от функции cos(x) с использованием указателя на функцию в качестве параметра.
115

double proiz(double x, double dx, double (*f)(double x) );
double fun(double z);
int main()
{
double x;
/* точка вычисления производной
*/
double dx;
/* приращение
*/
double z;
/* значение производной */
scanf("%f,%f",&x,&dx);
/* ввод значений x и dx
*/
z=proiz(x,dx,fun);
/* вызов функции */
printf("%f",z); /* печать значения производной
*/
return 0;
}
double proiz(double x,double dx, double (*f)(double z) )
{
/* функция вычисляющая производную */
double xk,xk1,pr;
xk=fun(x);
xk1=fun(x+dx);
pr=(xk1/xk-1e0)*xk/dx;
return pr;
}
double fun( double z)
{
/* функция от которой вычисляется производная */
return (cos(z));
}
Для вычисления производной от какой-либо другой функции можно изменить тело функции fun или использовать при вызове функции proiz имя другой функции. В частности, для вычисления производной от функции cos(x) можно вызвать функцию proiz в форме
z=proiz(x,dx,cos);
а для вычисления производной от функции sin(x) в форме
z=proiz(x,dx,sin);
Рекурсивные функции
Под рекурсивным определением подпрограммы или под рекурсией будем понимать такое описание (представление) подпрограммы, которое содержит внутри себя ссылку на определяемую подпрограмму. Другими словами, подпрограмма из своего тела осуществляет вызов непосредственно самой себя
(прямая рекурсия) с другими аргументами (параметрами), либо вызывает саму себя из других подпрограмм (функций или процедур), находящихся внутри тела рекурсивной подпрограммы (косвенная рекурсия). Далее, говоря о рекурсивных функциях или процедурах, будем подразумевать, что все сказанное относится и к тем и к другим, т.е. в общем случае – к подпрограммам.
116

Определение рекурсивных объектов в математике происходит по индукции. При этом сначала формулируется базис индукции, как рекурсивное определение исключительных случаев при вычислении функции, а затем шаг индукции, как рекурсивное правило построения того же объекта. Под индукцией
понимается метод доказательства утверждений, который строится на базе индукции при n = 0, 1, затем утверждение полагается правильным при n=n, и проводится доказательство для n+1.
Часто используется термин рекуррентные соотношения, который определяет математическое задание функции с помощью рекурсии. Основной задачей исследования рекурсивно заданных функций является получение f(n) в явной или как еще говорят «замкнутой» форме, т.е. в виде аналитически заданной функции, выражающейся через саму себя.
Важнейшим признаком любой рекурсивной функции является условие выхода из рекурсии. Такое условие выхода содержится, как правило, в самом начале рекурсивных функций и определяет, когда рекурсия должна быть закончена и применен базис индукции.
Рекурсивные функции очень часто используются в программировании, так как многие математические задачи носят рекурсивный характер. Решение задач с помощью рекурсивных функций бывает более изящным и коротким, чем не рекурсивное решение. Тем не менее, любая рекурсивная процедура или функция
имеет аналог без использования рекурсии, с помощью последовательных итераций (тезис Черча-Тьюринга). Изучению и исследованию рекурсивных функций посвящены целые разделы современной математики – теория
вычислений, теория вычислимости, теория алгоритмов, теория рекурсивных
функций. Практика показывает, что использовать в программировании рекурсивные процедуры и функции необходимо осторожно, поскольку непонимание механизмов рекурсии может привести к бесконечным циклам, зависанию программы, большим затратам времени выполнения и используемой памяти.
117

Пусть Р – рекурсивная подпрограмма, тогда выполнение действий в рекурсивной подпрограмме может быть организовано одним из следующих способов (рис.33):
int P();
{
P;
операторы;
}
int P();
{
операторы;
P;
}
int P();
{
операторы;
P;
операторы;
}
Рекурсивный подъём
Рекурсивный спуск
Рекурсивный спуск и рекурсивный подъём
Рис.33. Способы вызова рекурсивных подпрограмм
Пример 28. Представим в виде рекурсии функцию вычисления суммы двух натуральных чисел.
Сначала проанализируем задачу.
Пусть X=23 – это первое число, второе число Y=34. Сумма их равна:
F
1
= Sum (X, Y) = X+Y = Sum (23, 34)= 23+34=57
Уменьшим X на 1 и опять найдем сумму, X=23–1=22. Тогда
F
2
= Sum (X–1,Y) = X–1+Y = Sum (22,34)= 22+34=56=F
1
– 1
Видим, что при уменьшении первого слагаемого на 1, сумма тоже уменьшилась на 1. Последнее можно выразить так:
F
2
= Sum (X–1,Y) = (X–1) + Y = (X+Y) – 1= Sum (X,Y)–1.
Т.е. получили рекуррентное соотношение: Sum (X–1,Y) = Sum (X,Y)–1, отсюда:
Sum (X,Y) = Sum (X–1,Y)+1.
Т.е. для вычисления суммы некоторого числа X с числом Y нужно вычислить сумму предыдущего числа X – 1 c Y и прибавить к ней 1.
Теперь нужно определить граничные условия или условие завершения рекурсии (базис индукции). Мы видим, что на каждом шаге X уменьшается на 1.
До какой границы это нужно делать? Очевидно, пока Х не станет равным 0, т.к. по условию – числа натуральные. Но сумма любого числа с нулем дает в результате это число, т.е. граничное условие будет таким Sum(0,Y) = Y.
118

Итак, окончательная рекуррентная формула для сложения двух натуральных чисел такая:



>
+
=
=
0 .
X е с л и
1 ,
Y )
1 ,
-(X
S u m
0 ;
X е с л и
Y ,
Y )
( X ,
S u m
Для такой формулы просто написать рекурсивную функцию:
int SumXY (int x, int y)
{
if (x == 0) return(y);
else return(SumXY(x-1,y)+1);
}
Аналогично можно вывести рекуррентные соотношения для операций целочисленного (натурального) вычитания, умножения, деления, вычисления остатка от деления:



>
=
=
0 .
X е с л и
1 ,
-1)
-Y
( X ,
S u b
0 ;
Y е с л и
X ,
Y )
( X ,
S u b



>
+
=
=
0 .
X е с л и
X ,
1 )
-Y
( X ,
M u l t
1 ;
Y е с л и
X ,
Y )
( X ,
M u l t



>
+
≤
=
0 .
X е с л и
1 ,
Y )
Y ,
-
( X
D i v
Y ;
X е с л и
0 ,
Y )
( X ,
D i v




>
<
=
=
Y .
X е с л и
Y ) ,
Y ,
-
( X
M O D
Y ;
X е с л и
X ,
Y ;
X е с л и
,0
Y )
( X ,
M O D
Пример 29. Напишем программу для реализации этих рекурсивных функций:
int SumXY (int x, int y)
{
if (x == 0) return(y);
else return(SumXY(x-1,y)+1);
119

}
int SubXY (int x, int y)
{
if (y == 0) return(x);
else return(SubXY(x,y-1)-1);
}
int MultXY (int x, int y)
{
if (y == 1) return(x);
else return(MultXY(x,y-1)+x);
}
int DivXY (int x, int y)
{
if (x <= y) return(0);
else return(DivXY(x-y,y)+1);
}
int MODXY (int x, int y)
{
if (x < y) return(x);
else
if (x == y) return(0);
else return(MODXY(x-y,y));
}
int main()
{
int a,b;
printf("Введите целое положительное A:\n");
scanf("%i",&a);
printf("Введите целое положительное B:\n");
scanf("%i",&b);
printf(" A + B = %d" , SumXY(a,b));
printf(" A - B = %d" , SubXY(a,b));
printf(" A * B = %d" , MultXY(a,b));
printf(" A / B = %d" , DivXY(a,b));
printf(" A mod B = %d" , MODXY(a,b));
}
Пример 30. Напишем программу для реализации алгоритма Евклида нахождения наибольшего общего делителя (НОД) двух натуральных чисел.
Данный алгоритм был впервые описан в книге Евклида "Начала" (около 300 г. до н.э.). Суть алгоритма в следующем: пусть m и n одновременно неравные 0 целые неотрицательные числа и пусть m>n. Тогда если n=0, то НОД(m,n)=m; если же n≠0, то для чисел m, n, r (где r – остаток от деления m на n) выполняется равенство НОД(m,n)=НОД(n,r).
Из описания алгоритма выводим рекуррентное соотношение:
120




<
>
=
=
0 .
n е с л и n) ,
M O D
m
( n ,
N O D
0 ;
n е с л и m ,
n )
( m ,
N O D
Кроме того, вычислим на основе НОД наименьшее общее кратное (НОК), вспомнив формулу связи между НОД и НОК:
)
,
(
)
,
(
n
m
НОД
n
m
n
m
НОК
⋅
=
Напишем также функцию, которая вычисляет НОД без рекурсии. Для этого заметим, что мы можем использовать цикл, постоянно вычисляя остаток от деления до тех пор, пока он не станет равным 0.
Алгоритм будет такой:
int NODWhile (int m, int n)
{
int x;
while (n != 0)
{
m = m % n;
x = m;
m = n;
n = x;
//меняем местами m и n – по алгоритму Евклида
}
return(m);
}
Итак, программа, использующая написанные функции будет следующей:
int NODWhile (int m, int n)
{
int x;
while (n != 0)
{
m = m % n;
x =m;
m =n;
n =x;
// меняем местами m и n
}
return(m);
}
int NOD (int m, int n)
{
if (n == 0) return(m);
else return(NOD(n,m % n));
}
int main()
{
int m,n;
printf("Введите М\n");
scanf("%d", &m);
printf("Введите N\n");
scanf("%d", &n);
121

printf("n=%d m=%d NOD=%d\n", n, m, NOD(m,n));
printf("n=%d m=%d NODWhile=%d\n", n, m,NODWhile(m,n));
printf("n=%d m=%d NOK=%d\n", n, m, ceil(m*n/NOD(m,n)));
}
Пример 31. Напишем функции рекурсивного и не рекурсивного вычисления факториала числа и вывода чисел Фибоначчи.
Напомним, факториалом числа N называется функция, обозначаемая, как
N!, которая последовательно вычисляет произведение всех целых чисел от 1 до
N включительно, т.е.
N
N
N
⋅
−
⋅
⋅
⋅
⋅
=
)
1
(
3 2
1
!
. Для приближенного вычисления факториала больших чисел N может использоваться формула Стирлинга:
N
N
e
N
N
N
π
2
!
⋅
≈
Ряд Фибоначчи определяется так: это последовательность натуральных чисел, в которой первые два числа равны 1, а третье число ряда и последующие числа определяются, как сумма двух предыдущих чисел. Т.е. переходя от словесного описания можно сразу задать рекуррентную формулу для чисел
Фибоначчи:



>
+
=
=
.2
n е с л и
1) ,
-
( n
Ф
2 )
-
( n
Ф
1 , 2 ;
n е с л и
1,
( n )
Ф
Найдем рекуррентное соотношение для вычисления функции факториала.
Для этого заметим, что 1!=1, N!=(N-1)!
⋅
N. Таким, образом:



>
⋅
=
=
.1
N е с л и
N ,
1 ) !
-
( N
1 ;
N е с л и
1,
N !
Алгоритм вычисления чисел Фибоначчи без рекурсии основывается на том, что необходимо запомнить в переменных prelast, last два последних числа
Фибоначчи, чтобы вычислить следующее. Затем предыдущее можно «забыть» и перейти к вычислению следующего:
1. Начало
2.
prelast = 1; last = 1;
122

3.
Если n > 2, то сделать (n − 2) раз:
3.1.
c = prelast + last;
3.2.
prelast = last;
3.3.
last = c;
4.
Выдать ответ last;
5. Конец
Вычисление чисел Фибоначчи также осуществляется по формуле Бине:











 −
−



 +
=
n
n
n
Ф
2 5
1 2
5 1
5 1
)
(
. Это выражение всегда принимает целые значения.
Для вычисления факториала без рекурсии достаточно всего лишь в цикле перемножить подряд переменную цикла, сохраняя произведение в кумулятивной
(собирающей результаты) переменной.
Приведем код программы для вычисления указанных функций рекурсивно и без рекурсии.
int Fib (int n)
{
if ((n == 1) || (n == 2)) return(1);
else return(Fib(n-1)+Fib(n-2));
}
int FibCircle (int n)
{
int prelast,last,c,i;
if ((n == 1) || (n == 2)) return(1);
else
{
prelast = 1;
last = 1;
for(i=1;i
{
c = prelast + last;
prelast = last;
last = c;
}
}
return(last);
}
int FibBine (int n)
{
return(ceil(1/sqrt(5) * (pow((1+sqrt(5))/2,n) - pow((1-sqrt(5))/2,n))));
}
int Factorial (int n)
{
if (n == 1) return(1);
123

else return(Factorial(n-1)*n);
}
int FactorialNotRec (int n)
{
int i,f = 1;
for(i=1;i
{
f = f*i;
}
return(f);
}
int FactorialStirling (int n)
{
return(ceil(pow(n,n)*sqrt(2*M_PI*n)/exp(n)));
}
int _tmain(int argc, _TCHAR* argv[])
{
int i,n;
printf("Введите N:\n");
scanf("%d", &n);
for(i=1;i
{
printf("FibR[%d]\n", Fib(i));
printf("FibC[%d]\n", FibCircle(i));
printf("FibB[%d]\n", FibBine(i));
}
printf("Recurs : %d! = %d\n", n, Factorial(n));
printf("Circle : %d! = %d\n", FactorialNotRec(n));
printf("Stirling : %d! = %d\n", FactorialStirling(n));
system("pause");
}
Интересно, что числа Фибоначчи были придуманы математиком Леонардо
Фибоначчи в начале XXIII века, когда он размышлял над вопросом: «Сколько пар кроликов в один год родится от одной пары». В последствии в науке, искусстве, природе, во многих других приложениях и сферах деятельности человека числа Фибоначчи получили широкое распространение, порой даже мистическое. Например, выяснилось, что в расположении листьев на ветке семян подсолнечника, шишек сосны проявляет себя ряд Фибоначчи. Закономерности на основе ряда проявляются в энергетических переходах элементарных частиц, в строении некоторых химических соединений, в планетарных и космических системах, в генных структурах живых организмов. Закономерности на основе ряда Фибоначчи есть в строении отдельных органов человека и тела в целом, а также проявляются в биоритмах и функционировании головного мозга и
124

зрительного восприятия, в строении молекулы ДНК. С помощью этого ряда нашли закономерность и порядок в расстояниях между планетами солнечной системы. Однако один случай, который, казалось бы, противоречил закону: между Марсом и Юпитером не было планеты. Сосредоточенное наблюдение за этим участком неба привело к открытию пояса астероидов. Пропорции построения Египетских пирамид также основываются на ряде Фибоначчи. На основе чисел Фибоначчи получено золотое сечение (золотая симметрия) – это пропорции, применяемые в архитектуре, живописи. Например, известная картина Леонардо да Винчи «Мона Лиза» буквально «испещрена» такими пропорциями.
Приведем еще несколько примеров рекурсивного задания функций:
1.




+
=
+
+
−
+
−
=
=
=
∑
−
=
.1
)(
1
)2
(
)1
(
;0
,1 2
)
(
1 0
n
i
n
if
n
f
n
f
n
е с л и
n
f
2.



−⋅
=
=
=
) .1
(
2
;0
,1 2
)(
nf
n
е с л и
nf
n
3.



−⋅
=
=
=
) .1
(
;0
,1
)(
nf
a
n
е с л и
a
nf
n
4.




−
⋅−
=
=
=
=
) .
2
(
)1
(
;1
,2
;0
,1 2
)(
)(
nf
nf
n
е с л и
n
е с л и
nf
n
Ф
Первые два примера показывают, что одна и та же функция может иметь различные рекурсивные определения.
Анализ трудоемкости рекурсивных алгоритмов
125

Анализ трудоемкости рекурсивных реализаций алгоритмов связан с количеством операций, выполняемых при одном вызове функции, и количеством таких вызовов. Графическое представление порождаемой конкретным алгоритмом цепочки рекурсивных вызовов называется деревом
рекурсивных вызовов. Более детальное рассмотрение приводит к необходимости учета затрат как на организацию вызова функции и передачи параметров, так и на возврат вычисленных значений и передачу управления в точку вызова.
Можно заметить, что некоторая ветвь дерева рекурсивных вызовов обрывается при достижении такого значения передаваемого параметра, при котором функция может быть вычислена непосредственно, на основе базиса индукции. Таким образом, рекурсия эквивалентна конструкции цикла, в котором каждый проход есть выполнение рекурсивной функции с заданным параметром.
Рассмотрим пример для функции вычисления факториала N!=F(N) при
N=5 (рис.34).
Цепочка рекурсивных возвратов
(рекурсивный подъем)
Цепочка рекурсивных вызовов
(рекурсивный спуск)
126

Рис.34. Дерево рекурсии при вычислении факториала числа 5
При обращении к рекурсивной подпрограмме в памяти создаётся новая копия подпрограммы со всеми локальными переменными. Такие копии будут порождаться до выхода на граничное условие. Очевидно, в случае отсутствия граничного условия, неограниченный рост числа таких копий приведёт к аварийному завершению программы за счёт переполнения памяти (стека).
Порождение все новых копий рекурсивной подпрограммы до выхода на граничное условие называется рекурсивным спуском. Максимальное количество копий рекурсивной подпрограммы, которое одновременно может находиться в памяти компьютера, называется глубиной рекурсии. Завершение работы рекурсивных подпрограмм, вплоть до самой первой, инициировавшей рекурсивные вызовы, называется рекурсивным подъёмом.
Дерево рекурсивных вызовов может иметь и более сложную структуру, если на каждом вызове порождается несколько обращений. Например, дерево рекурсий для чисел Фибоначчи Ф(N) при N=6 представлено на рис.35:
При вычислении значения Ф(6) будут вызваны процедуры вычисления
Ф(5) и Ф(4). В свою очередь, для вычисления последних потребуется вычисление двух пар Ф(4), Ф(3) и Ф(3), Ф(2). Можно заметить, что Ф(3) вычисляется три раза, Ф(2) – пять раз. Если рассмотреть вычисление Ф(n) при больших n, то повторных вычислений будет очень много. Это и есть основной
недостаток рекурсии – повторные вычисления одних и тех же значений. Кроме
Ф(5)
Ф(6)
Ф(4)
Ф(4)
Ф(3)
Ф(3)
Ф(2)
Ф(1) Ф(2)
Ф(1)
Ф(2)
Ф(2)
Ф(1)
Ф(2)
Ф(3)
Рис.35. Дерево рекурсий для чисел Фибоначчи Ф(N) при N=6 127

того, с рекурсивными функциями может быть связана одна серьезная ошибка: дерево рекурсивных вызовов может оказаться бесконечным и компьютер
«зависнет». Важно, чтобы процесс сведения задачи к более простым операциям когда-нибудь заканчивался, т.е. существовало корректное условие выхода из рекурсии.
Следует понимать, что при каждом вызове любой подпрограммы в особую область памяти, выделенной операционной системой программе и называемой
стеком, записывается адрес инструкции, которая будет выполнена после завершения работы рекурсивной функции, а также параметры, передаваемые рекурсивной функции. Освобождение этой памяти происходит только при выходе из функции. Поэтому, если при вызове рекурсивной подпрограммы в стек заносится M байт, а размер стека N байт, то после K вызовов, примерно равном N/M – программа прекратит работу. Не смотря на то что, объемы оперативной памяти в настоящее время достаточно большие, существует вероятность переполнения стека при неправильных условиях завершения рекурсии, что грозит зависанием программы и операционной системы.
Чтобы избавиться от проблемы повторных вычислений, нужно запоминать найденные значения, например в массиве, и таким образом не вычислять их каждый раз заново. Для этого придётся активно использовать память, и осуществлять дополнительные проверки – вычислено или нет нужное число.
Тогда дерево рекурсий сведется к более простому виду (рис.36):
Например, для оптимизации рекурсивного алгоритма нахождения чисел
Фибоначчи необходимо добавить следующие действия:
•
создать глобальный массив FCalculated первоначально состоящий из нулей, в котором будут храниться уже найденные числа;
Ф(6)
Ф(4)
Ф(5)
Ф(3)
Ф(1)
Ф(2)
Рис.36. Дерево рекурсий при оптимизации рекурсивного алгоритма
128

•
после вычисления очередного числа Фибоначчи Ф(n) поместить его значение в FCalculated [n];
•
в начале рекурсивной процедуры сделать проверку на то, что
FCalculated [n] = 0. Если FCalculated [n] <> 0, то вернутся из рекурсивной функции со значением FCalculated [n] в качестве результата, иначе приступить к рекурсивному вычислению Ф (n).
Такая рекурсия с запоминанием результатов промежуточных шагов иногда называется динамическим программированием сверху.
const int NFib = 300;
//Максимальный размер массива с числами Фибоначчи
// описываем глобальный массив для запоминания результатов рекурсии
int FCalculated[NFib];
int FibDinam (int n)
{
if (FCalculated[n] != 0) return(FCalculated[n]);
else
{
if ((n == 1) || (n == 2)) return(1);
else
{
FCalculated[n]= FibDinam(n-1)+FibDinam(n-2);
return(FCalculated[n]);
}
}
}
int main()
{
int i,n;
// очищаем массив результатов рекурсии
for(i=1;i
{
FCalculated[i] = 0;
}
FCalculated[1] = 1;
FCalculated[2] = 1;
printf("введите N:\n");
scanf("%d", &n);
printf("FibD[%d] = %d\n", n, FibDinam(n));
}
Отметим, что если оценивать сложность рекурсивного алгоритма с запоминанием результатов, то он все равно уступает по скорости обычному алгоритму с итерациями, который был рассмотрен ранее, так как сложность алгоритма с итерациями – линейна, т.е. при использовании этого алгоритма для
129

вычисления n-го числа Фибоначчи потребуется n шагов. Это можно проверить на практике. Например, если на одном и том же компьютере выполнить при
N=85 три алгоритма нахождения чисел Фибоначчи: а) алгоритм с рекурсией (Fib); б) алгоритм с рекурсией с запоминанием результатов (FibDinam); с) алгоритм без рекурсии, с итерацией (FibCircle); то получим следующие временные результаты вычислений (примерно):
а) несколько минут; б) около секунды; с) практически мгновенно, т.е. не более секунды.
Эти результаты демонстрируют особенности использования рекурсивных алгоритмов.
Примечание. При выполнении программ и вычислении времени их выполнения использовался компьютер: Intel® Core™ 2 Duo CPU 3 Ghz, 4ГБ
ОЗУ.
Пример 32. Необходимо с помощью рекурсивной функции вычислить сумму элементов одномерного массива, который предварительно заполняется случайным образом с помощью стандартных функций генерации случайных чисел.
int Summa(int n, int A[100])
{
if (n = 0) return(0);
else return(A[n] + Summa(n-1,A));
}
int main()
{
int i,n;
int a[100];
printf("Количество элементов в массиве?\n");
scanf("%i", &n); //N<100
for(i=1;i
{
a[i] = -10 + rand();
printf("%d\n",a[i]);
}
printf("Сумма: %d\n", Summa(n,a));
}
130