Опорный конспект

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

являются те, которые используются в списке параметров прототипа функции. Если в списке параметров прототипа функции используется имя, компилятор его просто игнорирует. Идентификатор, используемый в прототипе функции, можно повторно использовать где угодно в программе, не опасаясь двусмысленности.

6.4. Рекурсия

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

Рекурсивная задача в общем случае разбивается на ряд этапов. Для решения задачи вызывается рекурсивная функция. Эта функция знает, как решать только простейшую часть задачи – так называемую базовую задачу. Если эта функция вызывается для решения базовой задачи, она просто возвращает результат. Если функция вызывается для решения более сложной задачи, она делит эту задачу на две части: одну часть, которую функция решать умеет, и другую, которую функция решать не умеет. Чтобы сделать рекурсию выполнимой, последняя часть должна быть похожа на исходную задачу, но быть по сравнению с ней несколько проще или несколько меньше. Поскольку эта новая задача подобна исходной, функция вызывает новую копию самой себя, чтобы начать работать над меньшей проблемой – это называется рекурсивным вызовом или шагом рекурсии. Шаг рекурсии включает ключевое слово return, так как в дальнейшем его результат будет объединен с той частью задачи, которую функция решать умеет, и сформируется конечный результат, который будет передан обратно в исходное место вызова.

Шаг рекурсии выполняется до тех пор, пока исходное обращение к функции не закрыто, т.е. пока еще не закончено выполнение функции. Шаг рекурсии может приводить к большому числу таких рекурсивных вызовов, поскольку функция продолжает деление каждой новой подзадачи на две части. Чтобы завершить процесс рекурсии, каждый раз, как функция вызывает саму себя с несколько упрощенной версией исходной задачи, должна формироваться последовательность все меньших и меньших задач, в конце концов, сходящаяся к базовой задаче. В этот момент функция распознает базовую задачу, возвращает результат предыдущей копии функции и последовательность возвратов повторяет весь путь назад, пока не дойдет до первоначального вызова и не возвратит конечный результат в main (см. рис. 6.7)

Факториал n!:

n! = n*(n-1)*(n-2)*…*1

Факториал может быть вычислен не рекурсивно, а итеративно с помощью оператора for:

factorial = 1;

for(int counter = number; counter >=1; counter--)

53

Рис. 6.7. Рекурсивное дерево для вычисления факториала

Рекурсивное определение функции факториал дается следующим соотношени-

ем: n! = n*(n-1)!

unsigned long factorial(unsigned long number)

{

if (number <=1) return 1;

else

return number * factorial (number-1);

}

Рис. 6.8. Рекурсивное вычисление факториала

Последовательность чисел Фибоначчи

Это пример как не надо использовать рекурсию.

Последовательность чисел Фибоначчи рекурсивно можно определить следующим образом:

fibonacci(0) = 0 fibonacci(1) = 0

54

fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2)

Рис. 6.9. Формула для числа Фибоначчи

Функция, рекурсивно вычисляющая число Фибоначчи:

unsigned long fibonacci (insigned long n)

{

if(n == 0 || n == 1) return n;

else

return fibonacci (n-1) + fibonacci (n-2);

}

Рис.6.20. Рекурсивное вычисление числа Фибоначчи

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

Количество рекурсивных вызовов, которое должно быть выполнено для вычисления n-го числа Фибоначчи, оказывается порядка 2n. Поэтому поиск числа Фибоначчи обычно осуществляют итеративным путем

F(3)

Рис. 6.11. Рекурсивное дерево для вычисления числа Фибоначчи

Далее представлена программа [5], реализующая алгоритм быстрой сортировки. Стратегия быстрой сортировки основана на принципе «разделяй и властвуй». Первое, что делает быстрая сортировка – это выбор разделяющего значения из элементов массива. В качестве разделяющего элемента определяется медиана массива. Медиана – это среднее значение из первого, последнего и серединного элементов массива. Следующий шаг – разбиение массива на два подмассива с помощью выбранного разделяющего значения. После этого разделя-

55

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

#include <stdlib.h> #include <time.h> #include <iostream> #include <assert.h> using namespace std;

//======================================================== void swap (int &a, int &b) //перестановка двух элементов массива

{

int t = a; a = b;

b = t;

}

//======================================================== void Out(int * arr, int col) // вывод на экран нашего

{

}

//========================================================

//В качестве разделяющего элемента выбирается среднее //левого, серединного или правого значения

int get_pe(int *arr, int lower, int upper){ assert((upper-lower)>1);

int mid = (lower+upper)/2; if(arr[lower]<=arr[mid]) {

if(arr[mid]<=arr[upper]) return mid;

else if(arr[upper]<=arr[lower]) return lower;

else

return upper;

}

else { if(arr[lower]<=arr[upper])

return lower;

else if(arr[upper]<=arr[mid]) return mid;

else

return upper;

}

}

//========================================================

Рис. 6.12. Вспомогательные функции алгоритма быстрой сортировки

56

//Функция разбивает подмассив, ограниченный start и end, на два меньших //подмассива таких, что все элементы левого подмассива меньше, // а все элементы правого подмассива больше разделяющего значения

//Сам разделяющий элемент оказывается на своем окончательном месте //в отсортированном массиве. Возвращает индекс позиции разделяющего //элемента

int partition(int * arr, int start, int end, int pe_index)

{

//сохранить разделяющее значение и поместить //разделяющий элемент в крайнюю правую позицию int pe = arr[pe_index];

swap(arr[pe_index], arr[end]);

//инициализировать head и tail так, чтобы они указывали //на начальный и предпоследний элементы массива int head = start, tail = end -1;

while(true) //входим в бесконечный цикл

{

//увеличить head, пока не достигнем элемента, //большего или равного разделяющему while(arr[head]<pe)

++head;

//уменьшить tail, пока не достигнем элемента, //меньшего или равного разделяющему while((arr[tail]>pe)&&(tail>start))

--tail;

//обменять head и tail, если они уже не скрестились. //принудительный инкремент/декремент индексов head/tail //после обмена предотвратит бесконечный цикл в случае, если //они оба ссылаются на разделяющее значение if(head>=tail)

break; swap(arr[head++],arr[tail--]);

}

swap(arr[head], arr[end]); return head;

}

//========================================================

Рис. 6.13. Функция «устанавливает» на место разделяющий элемент

57

//Функция управляет ходом рекурсии. После получения разделяющего // элемента разбивает массив на два подмассива, вызывая partition(). //Затем она рекурсивно вызывает саму себя для сортировки каждого //из подмассивов

void quick_sort(int* arr, int head, int tail)

{

int diff = tail-head;

//если массив из одного элемента, то выходим if(diff<1) return;

//специальный случай для двухэлементного массива if(1==diff)

{

if(arr[head]>arr[tail])

swap(arr[head],arr[tail]);

return;

}

int pe_index = get_pe(arr,head,tail);

int mid = partition(arr, head, tail, pe_index); assert((mid>=head)&&(mid<=tail));

//элемент с индексом mid содержит теперь разделяющее значение //и занимает правильную позицию.

//Сортировать левый и правый подмассивы quick_sort(arr, head, mid-1); quick_sort(arr, mid+1, tail);

}

//========================================================

//главная функция - заполнение массива, //вызов функции сортировки и вывод на экран int main()

{

const int col_el=10000; int arr[col_el]; srand(time(0));

rand();

for (int i=0; i<col_el ; i++) arr[i]= rand()-16384;

cout << "Before :"<<endl; Out(arr, col_el); quick_sort(arr, 0, col_el-1); cout << "Result is :"<<endl; Out(arr, col_el);

return 0;

}

//************************************************

Рис. 6.14. Рекурсивная функция сортировки, и главная функция программы

58

6.5. Ссылки и ссылочные параметры

Во многих языках программирования имеются два способа обращения к функциям – вызов по значению и вызов по ссылке [1].

В С++ существуют три способа передачи аргументов в функции:

1)вызов по значению;

2)вызов по ссылке с аргументами ссылками;

3)вызов по ссылке с аргументами указателями.

Когда аргумент передается вызовом по значению, создается копия аргумента, и она передается вызываемой функции. Изменения копии не влияет на значение оригинала в операторе вызова. Это предотвращает случайный побочный эффект, который так сильно мешает развитию надежного и корректного программного обеспечения. Все аргументы, которые передавались в функции до этого момента, передавались вызовом по значению. Один из недостатков вызова по значению состоит в том, что если передается большой элемент данных, это может привести к значительным потерям времени выполнения.

#include <iostream> using namespace std;

int squareByValue(int);

void squareByReference(int &);

int main(){

int x = 2, z = 4;

cout << "Before:" << endl; cout << "x= " << x << endl; cout << "z= " << z << endl; squareByValue(x); squareByReference(z);

cout << "After:" << endl; cout << "x= " << x << endl; cout << "z= " << z << endl; return 0;

}

int squareByValue(int a){ return a *=a;}

void squareByReference(int &cRef){ cRef *=cRef;}

Рис. 6.15. Передача параметра по значению и по ссылке

Ссылочный параметр – это скрытый указатель, псевдоним соответствующего аргумента. Чтобы показать, что параметр функции передан по ссылке, после типа параметра в прототипе функции ставится символ амперсанда (&); такое же обозначение используется в списке типов параметров в заголовке функции.

59

Например, объявление int &count в заголовке функции может читаться как «count является ссылкой на int». В вызове функции достаточно указать имя переменной, и она будет передана по ссылке. Тогда упоминание в теле вызываемой функции переменной по имени ее параметра в действительности является обращением к исходной переменной в вызывающей функции, и эта исходная переменная может быть изменена непосредственно вызываемой функцией (см.

рис. 6.15.)

Ссылки можно также использовать как псевдонимы для других переменных внутри функций

int count = 1; //объявление целой переменной count int &cRef = count; //создание cRef как псевдонима для count

++cRef;

Рис. 6.16. Создание ссылки внутри функции

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

Вызов функций по ссылке с аргументами указателями

Ранее было проведено сравнение и сопоставление вызовов по значению и по ссылке с аргументами ссылки. Сейчас рассмотрим на вызове по ссылке с аргументами указателями.

return можно использовать для возвращения одного значения из вызываемой функции вызывающему оператору (или для передачи управления из вызываемой функции без возвращения какого-либо значения). Параметры могут быть переданы функции с использованием аргументов ссылок, чтобы дать возможность функции модифицировать исходные значения аргументов (таким образом, из функции может быть «возвращено» более одного значения), или чтобы передать функции большие объекты и избежать накладных расходов, сопутствующих передаче объектов вызовом по значению. Указатели, подобно ссылкам, тоже можно использовать для модификации одного или более значений переменных в вызывающем операторе, или передавать указатели на большие объекты данных, чтобы избежать накладных расходов, сопутствующих передаче объектов по значению.

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

60

массива – это начальный адрес массива в памяти. При передаче функции адреса переменной может использоваться операция косвенной адресации (*) для модификации значения (если значение не объявлено как const) ячейки в памяти вызывающего оператора.

На рис. 6.17 представлена программа с двумя вариантами функции, которая возводит в куб целое число – CubeByValue и CubeByReference. Первая функция передает переменную number функции CubeByValue вызовом по значению. Функция CubeByValue возводит в куб свой аргумент и возвращает новое значение в main, используя оператор return. Новое значение присваивается переменной number в main. Ключевой момент вызова по значению состоит в том, что программисту предоставляется возможность анализировать результат вызова функции перед модификацией значения переменной. Например, в первой программе можно было бы сохранить результат, возвращаемый CubeByValue в другой переменной, исследовать его значение, и после этого присвоить результат переменной number.

Вторая функция передает переменную number по ссылке – в функцию CubeByReference передается адрес number. Функция CubeByReference в

качестве аргумента получает nPtr (указатель на int). Функция разыменовывает указатель и возводит в куб значение, на которое указывает nPtr. Это изменяет значение number в main.

int CubeByValue (int);

void CubeByReference (int*);

int main(){

int number1; int number2; number1 = 5; number2 = 5;

cout << "number1 before " << number1 << endl; number1 = CubeByValue (number1);

cout << "number1 after " << number1 << endl;; cout << "number2 before " << number2 << endl;

CubeByReference (&number2);

cout << "number2 after " << number2 << endl; return 0;

}

int CubeByValue (int n){ return n*n*n;}

void CubeByReference (int* nPtr){

*nPtr = *nPtr **nPtr**nPtr;}

Рис. 6.17. Программа, иллюстрирующая передачу параметра по значению и по ссылке с аргументом указателем

61

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

6.6. Использование спецификатора const с указателями

Спецификация const дает возможность программисту информировать компилятор о том, что значение данной переменной не должно изменяться [1].

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

Существуют четыре способа передачи в функцию указателя:

1)неконстантный указатель на неконстантные данные;

2)неконстантный указатель на константные данные;

3)константный указатель на неконстантные данные;

4)константный указатель на константные данные.

Каждая комбинация обеспечивает доступ с разным уровнем привилегий. Наивысший уровень доступа предоставляется неконстантным указателям на неконстантные данные – данные можно модифицировать посредством разыменования указателя, а сам указатель может быть модифицирован, чтобы он указывал на другие данные. Объявление неконстантного указателя на неконстантные данные не содержит const.

Неконстантный указатель на константные данные – это указатель, который можно модифицировать, чтобы указывать на любые элементы данных подходящего типа, но данные, на которые он ссылается, не могут быть модифицированы. Такой указатель можно было бы использовать, чтобы передать в качестве аргументов массивы функции, которая будет обрабатывать каждый элемент массива без модификации данных (рис. 6.18).

#include <iostream> using namespace std;

void CubeByReference (const int*); int main(){

int number2 = 5;

cout << "number2 before " << number2 << endl; CubeByReference (&number2);

cout << "number2 after " << number2 << endl; return 0;

}

void CubeByReference (const int* nPtr){ int number = 20;

nPtr = &number;

cout << *nPtr**nPtr**nPtr << endl;

//*nPtr= *nPtr**nPtr**nPtr; нельзя изменять данные с помощью //операции разыменования указателя

number = 1;

cout << *nPtr**nPtr**nPtr << endl;}

Рис. 6.18. Использование неконстантного указателя на константные данные

62