Функции с переменным количеством параметров

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

тип_функции имя_функции (спецификация_явных_параметров,...);

Здесь тип_функции - тип возвращаемого функцией значения; имя_функции - имя функции; спецификация_явных_параметров - список спецификаций отдельных параметров, количество и типы которых фиксированы и известны в момент компиляции. Эти параметры можно назвать обязательными. После списка явных (обязательных) параметров ставится необязательная запятая, а затем многоточие, извещающее компилятор, что дальнейший контроль соответствия количества и типов параметров при обработке вызова функции проводить не нужно. Сложность в том, что у переменного списка параметров нет даже имени, поэтому непонятно, как найти его начало и где этот список заканчивается.

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

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

//Программа 6.2

#include "stdafx.h"

#include <iostream> //Функция суммирует значения своих параметров типа int

long summa(int k,...){ // k - число суммируемых параметров

int *pik = &k;

long total = 0;

for(; k; k--) total += *(++pik);

return total;

}

void main() {

std::cout<< "\n summa(2, 6, 4) = " << summa(2,6,4);

std::cout<< "\n summa(6, 1, 2, 3, 4, 5, 6) = " << summa(6,1,2,3,4,5,6);

getchar();

}

Результат выполнения программы:

summa(2, 6, 4) = 10

summa(6, 1, 2, 3, 4, 5, 6) = 21

Для доступа к списку параметров используется указатель pik типа int *. Вначале ему присваивается адрес явно заданного параметра k, т.e. он устанавливается на начало списка параметров в памяти (в стеке). Затем в цикле указатель pik перемещается по адресам следующих фактических параметров, соответствующих неявным формальным параметрам. С помощью разыменования *pik выполняется выборка их значений. Параметром цикла суммирования служит аргумент k, значение которого уменьшается на 1 после каждой итерации и, наконец, становится нулевым. Особенность функции возможность работы только с целочисленными фактическими параметрами, так как указатель pik после обработки значения очередного параметра "перемещается вперед" на величину sizeof (int) и должен быть всегда установлен на начало следующего параметра.

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

//Программа 6.3

#include "stdafx.h"

#include <iostream>

// Функция вычисляет произведение параметров:

double prod(double arg,...){

double aa = 1.0; // Формируемое произведение

double* prt = &arg; /* Настроили указатель на первый параметр*/

if (*prt == 0.0) return 0.0;

for(;*prt; prt++) aa *= *prt;

return aa;

}

void main(){

double prod(double,...); // Прототип функции

std::cout <<"\n prod(2., 4., 3., 0.0) =" <<prod(2.,4.,3., 0.0);

std::cout <<"\n prod(1.5, 2.0, 3.0, 0.0) = ";

std::cout<<prod(1.5, 2.0, 3.0,0.0);

std::cout<<"\n prod(1.4, 3.0, 0.0, 16.0, 84.3, 0.0) = ";

std::cout << prod(1.4, 3.0, 0.0, 16.0, 84.3, 0.0);

std::cout << "\n prod (0.0) = " << prod (0.0);

getchar();

}

Результат выполнения программы:

prod(2., 4., 3., 0.0) = 24

prod(1.5, 2.0, 3.0, 0.0) = 9

prod(1.4, 3.0, 0.0, 16.0, 84.3, 0.0) = 4.2

prod(0.0) = 0

В функции prod перемещение указателя prt по списку фактических параметров выполняется всегда за счет изменения prt на величину sizeof (double). Поэтому все фактические параметры при обращении к функции prod () должны иметь тип double. В вызовах функции проиллюстрированы некоторые варианты задания параметров. Обратите внимание на вариант с нулевым значением параметра в середине списка. Параметры вслед за этим значением игнорируются.

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

В приведенных примерах функций с изменяемыми списками параметров перебор параметров выполнялся с использованием адресной арифметики и явным применением указателей нужных типов. К проиллюстрированному способу перехода от одного параметра к другому нужно относиться с осторожностью. Дело в том, что при обращении к функции ее параметры помещаются в стек, причем порядок их размещения в стеке зависит от реализации компилятора. Более того, в компиляторах имеются опции, позволяющие изменять последовательность помещения значений параметров в стек. Стандартная для языка Си++ последовательность размещения параметров в стеке предполагает, что первым обрабатывается и помещается в стек последний из параметров функции. При этом у него оказывается максимальный адрес (так стек устроен в реализациях на IBM PC). Противоположный порядок обработки и помещения в стек будет у функций, определенных и описанных с модификатором pascal. Этот модификатор и его антипод модификатор cdecl являются дополнительными ключевыми словами, определенными для компиляторов ТСи++ и ВСи++.

 

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

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

long fact(int k){ 

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

}