Область действия

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

Идентификатор, объявленный вне любой функции(на внешнем уровне), имеетобласть действия файл. Такой идентификатор известен всем функциям от точки его объявления до конца файла.

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

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

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

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--)

factorial *= counter;

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

Рис. 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

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-го числа Фибоначчи, оказывается порядка2ⁿ. Поэтому поиск числа Фибоначчи обычно осуществляют итеративным путем

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

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

#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) // вывод на экран нашего

{

for (int i=0; i<col; i++) // массива после сортировки

cout << arr [i] <<" ";

cout << endl;

}

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

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

//левого, серединного или правого значения

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. Вспомогательные функции алгоритма быстрой сортировки

//Функция разбивает подмассив, ограниченный 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. Функция «устанавливает» на место разделяющий элемент

//Функция управляет ходом рекурсии. После получения разделяющего

// элемента разбивает массив на два подмассива, вызывая 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. Рекурсивная функция сортировки, и главная функция программы