6.3. Рекурсивные функции

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

longfact(intk){

if (k < 0) return 0;

if (k == 0) return 1;

return k * fact(k-l);

}

Для отрицательного аргумента результат по определению факториала не существует. В этом случае функция возвратит нулевое значение. Для нулевого параметра функция возвращает значение 1, так как по определению, 0! равен 1. В противном случае вызывается та же функция с уменьшенным на 1 значением параметра и результат умножается на текущее значение параметра. Тем самым для положительного значения параметра k организуется вычисление произведения

k* (k-l) * (k-2) *...*3*2*1*1

Обратите внимание, что последовательность рекурсивных обращений к функции fact прерывается только при вызове fact(0). Именно этот вызов приводит к последнему значению 1 в произведении, так как последнее выражение, из которого вызывается функция, имеет вид:

1 * fact(1-1)

Поскольку в теле самой функции fact() присутствует её вызов, то по определению такую функцию называют прямой рекурсивной функцией.

В качестве еще одного примера рекурсии рассмотрим функцию QuickSort(), реализующую алгоритм быстрой сортировки.

//Программа 6.4

#include "stdafx.h"

#include <stdio.h>

#include <stdlib.h>

#define DIMENSION 100

void QuickSort(int array[], int First, int Last)

{

int Temp, LowerBoundary, UpperBoundary, Separator;

LowerBoundary = First;

UpperBoundary = Last;

Separator = array[(First + Last) / 2];

do{

while (array[LowerBoundary] < Separator) LowerBoundary++;

while (array[UpperBoundary] > Separator) UpperBoundary--;

if (LowerBoundary <= UpperBoundary){

Temp = array[LowerBoundary];

array[LowerBoundary++] = array[UpperBoundary];

array[UpperBoundary--] = Temp;

}

} while (LowerBoundary <= UpperBoundary);

if (First<UpperBoundary)QuickSort(array,First,UpperBoundary);

if (LowerBoundary<Last) QuickSort(array, LowerBoundary, Last);

}

void main()

{

int array[DIMENSION], i = 0;

for (; i < DIMENSION; array[i++] = rand()%1000) ;

QuickSort(array, 0, DIMENSION -1);

printf("\n\n");

for (i = 0; i < DIMENSION; printf("\n%d", array[i++])) ;

getchar();

}

6.4. Подставляемые (инлайн-) функции

Некоторые функции в языке Си++ можно определить с использованием специального служебного слова inline. Спецификатор inline позволяет определить функцию как встраиваемую, иначе говоря подставляемую или "открыто подставляемую", или "инлайн-функцию". Например, следующая функция определена как подставляемая:

inlinefloatmodule(floatx= 0,floatу = 0) {

returnsqrt(x*x+ у * у);

}

Функция module () возвращает значение типа float, равное "расстоянию" от начала координат на плоскости до точки с координатами (х,у), определяемыми значениями фактических параметров. В теле функции вызывается библиотечная функция sqrt() для вычисления вещественного значения квадратного корня положительного аргумента. Так как подкоренное выражение в функции всегда неотрицательно, то специальных проверок не требуется. Обрабатывая каждый вызов встраиваемой функции, компилятор "пытается" подставить в текст программы код операторов ее тела. Спецификатор inline для функций, не принадлежащих классам, определяет для функций внутреннее связывание. Во всех других отношениях подставляемая функция является обычной функцией, т.е. спецификатор inline в общем случае не влияет на результаты вызова функции, она имеет обычный синтаксис определения и описания, подчиняется всем правилам контроля типов и области действия. Однако вместо команд передачи управления единственному экземпляру тела функции компилятор в каждое место вызова функции помещает соответствующим образом настроенные команды кода операторов тела функции. Тем самым при многократных вызовах подставляемой функции размеры программы могут увеличиться, однако исключаются затраты на передачи управления к вызываемой функции и возвраты из нее. Как отмечает проект стандарта Си++, кроме экономии времени при выполнении программы, подстановка функции позволяет проводить оптимизацию ее кода в контексте, окружающем вызов, что в ином случае невозможно.

Наиболее эффективно использовать подставляемые функции в тех случаях, когда тело функции состоит всего из нескольких операторов. Идеальными претендентами на определение со спецификатором inline являются несложные короткие функции. Удобны для подстановки функции, основное назначение которых вызов других функций либо выполнение преобразований типов.

Так как компилятор встраивает код подставляемой функции вместо ее вызова, то определение функции со спецификатором inline должно находиться в том же модуле, что и обращение к ней, и размещается до первого вызова. Синтаксис языка не гарантирует обязательной подстановки кода функции для каждого вызова функции со спецификатором inline.

Проект стандарта перечисляет следующие причины, по которым функция со спецификатором inline будет трактоваться как обычная функция (не подставляемая):

• встраиваемая функция слишком велика, чтобы выполнить ее подстановку;

• встраиваемая функция рекурсивна;

• обращение к встраиваемой функции в программе размещено до ее определения;

• встраиваемая функция вызывается более одного раза в выражении;

• встраиваемая функция содержит цикл, переключатель или оператор перехода.

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