7.5. Рекурсия

Функция, которая прямо или косвенно вызывает сама себя, называется рекурсивной.

int rgcd( int vl, int v2 )

{

if ( v2 != 0 )

return rgcd( v2, vl%v2 ); return vl;

Например:

}

Такая функция обязательно должна определять условие окончания, в противном случае рекурсия будет продолжаться бесконечно. Подобную ошибку так иногда и называют – бесконечная рекурсия. Для rgcd() условием окончания является равенство нулю остатка.

Вызов

rgcd( 15, 123 );

возвращает 3 (см. табл. 7.1).

Таблица 7.1. Трассировка вызова rgcd (15,123)

Последний вызов,

rgcd(3,0);

удовлетворяет условию окончания. Функция возвращает наибольший общий делитель, он же возвращается и каждым предшествующим вызовом. Говорят, что значение всплывает (percolates) вверх, пока управление не вернется в функцию, вызвавшую rgcd() в первый раз.

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

Приведем пример. Факториалом числа n является произведение натуральных чисел от 1 до n. Так, факториал 5 равен 120: 1 × 2 × 3 × 4 × 5 = 120.

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

Рекурсия обрывается по достижении val значения 1.

Упражнение 7.12

Перепишите factorial() как итеративную функцию.

Упражнение 7.13

Что произойдет, если условием окончания factorial() будет следующее:

if ( val != 0 )

7.6. Встроенные функции

int min( int vl, int v2 )

{

return( vl < v2 ? vl : v2 );

Рассмотрим следующую функцию min():

}

Преимущества определения функции для такой небольшой операции таковы:

∙как правило, проще прочесть и интерпретировать вызов min(), чем читать условный оператор и вникать в смысл его действий, особенно если v1 и v2 являются сложными выражениями;

∙модифицировать одну локализованную реализацию в приложении легче, чем

300.Например, если будет решено изменить проверку на:

( vl == v2 || vl < v2 )

поиск каждого ее вхождения будет утомительным и с большой долей вероятности приведет к ошибкам;

∙семантика единообразна. Все проверки выполняются одинаково;

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

Однако этот подход имеет один недостаток: вызов функции происходит медленнее, чем непосредственное вычисление условного оператора. Необходимо скопировать два аргумента, запомнить содержимое машинных регистров и передать управление в другое место программы. Решение дают встроенные функции. Встроенная функция “подставляется по месту” в каждой точке своего вызова. Например:

int minVa12 = min( i, j );

заменяется при компиляции на

int minVal2 = i < j ? i : j;

Таким образом, не требуется тратить время на реализацию min() в виде функции.

Функция min() объявляется как встроенная с помощью ключевого слова inline перед типом возвращаемого значения в объявлении или определении:

inline int min( int vl, int v2 ) { /* ... */ }

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

крайне важен для поддержки концепции сокрытия информации при разработке абстрактных типов данных. Например, встроенной объявлена функция-член size() в классе IntArray из раздела 2.3.

Встроенная функция должна быть видна компилятору в месте вызова. В отличие от обычной, такая функция определяется в каждом исходном файле, где есть обращения к ней. Конечно же, определения одной и той же встроенной функции в разных файлах должны совпадать. Если программа содержит два исходных файла compute.C и draw.C, не нужно писать для них разные реализации функции min(). Если определения функции различаются, программа становится нестабильной: неизвестно, какое из них будет выбрано для каждого вызова, если компилятор не стал встраивать эту функцию.

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

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

Поскольку min() является общеупотребительной операцией, реализация ее входит в стандартную библиотеку С++; это один из обобщенных алгоритмов, описанных в главе 12 и в Приложении. Функция min() реализована как шаблон, что позволяет ей работать с операндами арифметического типа, отличного от int. (Шаблоны функций рассматриваются в главе 10.)

7.7. Директива связывания extern "C" A

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

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

//директива связывания в форме простой инструкции extern "C" void exit(int);

//директива связывания в форме составной инструкции extern "C" {

int printf( const char* ... ); int scanf( const char* ... );

}

// директива связывания в форме составной инструкции extern "C" {

#include <cmath>

}

Первая форма такой директивы состоит из ключевого слова extern, за которым следует строковый литерал, а за ним – “обычное” объявление функции. Хотя функция написана на другом языке, проверка типов вызова выполняется полностью. Несколько объявлений

функций могут быть помещены в фигурные скобки составной инструкции директивы связывания – второй формы этой директивы. Скобки отмечают те объявления, к которым она относится, не ограничивая их видимости, как в случае обычной составной инструкции. Составная инструкция extern "C" в предыдущем примере говорит только о том, что функции printf() и scanf() написаны на языке С. Во всех остальных отношениях эти объявления работают точно так же, как если бы они были расположены вне инструкции.

Если в фигурные скобки составной директивы связывания помещается директива препроцессора #include, все объявленные во включаемом заголовочном файле функции рассматриваются как написанные на языке, указанном в этой директиве. В предыдущем примере все функции из заголовочного файла cmath написаны на языке С.

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

int main() {

//ошибка: директива связывания не может появиться

//внутри тела функции

extern "C" double sqrt( double ); double getValue(); //правильно

double result = sqrt ( getValue() ); //...

return 0;

кода вызывает ошибку компиляции:

}

Если мы переместим директиву так, чтобы она оказалась вне тела main(), программа

double result = sqrt ( getValue() ); //...

return 0;

откомпилируется правильно:

}

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

Как сделать С++ функцию доступной для программы на С? Директива extern "C"

// функция calc() может быть вызвана из программы на C

поможет и в этом:

extern "C" double calc( double dparm ) { /* ... */ }

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

// ---- myMath.h ----

extern "C" double calc( double );

//---- myMath.C ----

//объявление calc() в myMath.h #include "myMath.h"

//определение функции extern "C" calc()

//функция calc() может быть вызвана из программы на C

распространяется и на все последующие объявления. Например: double calc( double dparm ) { // ... }

В данном разделе мы видели примеры директивы связывания extern "C" только для языка С. Это единственный внешний язык, поддержку которого гарантирует стандарт С++. Конкретная реализация может поддерживать связь и с другими языками. Например, extern "Ada" для функций, написанных на языке Ada; extern "FORTRAN" для языка FORTRAN и т.д. Мы описали один из случаев использования ключевого слова extern в С++. В разделе 8.2 мы покажем, что это слово имеет и другое назначение в объявлениях функций и объектов.

Упражнение 7.14

exit(), printf(), malloc(), strcpy() и strlen() являются функциями из библиотеки С. Модифицируйте приведенную ниже С-программу так, чтобы она компилировалась и связывалась в С++.

const char *str = "hello";

void *malloc( int );

char *strcpy( char *, const char * ); int printf( const char *, ... );

int exit( int );

int strlen( const char * );

int main()

{/* программа на языке С */

char* s = malloc( strlen(str)+l ); strcpy( s, str );

printf( "%s, world\n", s ); exit( 0 );

}

7.8. Функция main(): разбор параметров командной

строки

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

prog -d -o of lie dataO

Фактические параметры являются аргументами функции main() и могут быть получены из массива C-строк с именем argv; мы покажем, как их использовать.

Во всех предыдущих примерах определение main() содержало пустой список:

int main() { ... }

Развернутая сигнатура main() позволяет получить доступ к параметрам, которые были заданы пользователем в командной строке:

int main( int argc, char *argv[] ){...}

argc содержит их количество, а argv – C-строки, представляющие собой отдельные значения (в командной строке они разделяются пробелами). Скажем, при запуске

команды

prog -d -o ofile data0

argc получает значение 5, а argv включает следующие строки:

argv[ 0 ] = "prog"; argv[ 1 ] = "-d"; argv[ 2 ] = "-o"; argv[ 3 ] = "ofile"; argv[ 4 ] = "dataO";

В argv[0] всегда входит имя команды (программы). Элементы с индексами от 1 до argc-1 служат параметрами.

Посмотрим, как можно извлечь и использовать значения, помещенные в argv. Пусть

prog [-d] [-h] [-v]

[-o output_file] [-l limit_value] file_name

программа из нашего примера вызывается таким образом:

[ file_name [file_name [ ... ]]]

Параметры в квадратных скобках являются необязательными. Вот, например, запуск программы с их минимальным количеством – одним лишь именем файла:

prog chap1.doc

prog -l 1024 -o chap1-2.out chapl.doc chap2.doc prog d chap3.doc

Но можно запускать и так: prog -l 512 -d chap4.doc

При разборе параметров командной строки выполняются следующие основные шаги:

1. По очереди извлечь каждый параметр из argv. Мы используем для этого цикл for с

for ( int ix = 1; ix < argc; ++ix ) { char *pchar = argv[ ix ];

// ...

начальным индексом 1 (пропуская, таким образом, имя программы):

}

2.Определить тип параметра. Если строка начинается с дефиса (-), это одна из опций { h, d, v, l, o}. В противном случае это может быть либо значение, ассоциированное с опцией (максимальный размер для -l, имя выходного файла для -o), либо имя входного файла. Чтобы определить, начинается ли строка с дефиса, используем

switch ( pchar[ 0 ] ) { case '-': {

//-h, -d, -v, -l, -o

}

default: {

//имена входных файлов ...

}

инструкцию switch:

}

Реализуем обработку двух случаев пункта 2.

Если строка начинается с дефиса, мы используем switch по следующему символу для

case '-': {

switch( pchar[ 1 ] )

{

case 'd':

// обработка опции debug break;

case 'v':

// обработка опции version break;

case 'h':

// обработка опции help break;

case 'o':

// приготовимся обработать выходной файл break;

case 'l':

// приготовимся обработать макс.размер break;

default:

//неопознанная опция:

//сообщить об ошибке и завершить выполнение

}

определения конкретной опции. Вот общая схема этой части программы:

}

Опция -d задает необходимость отладки. Ее обработка заключается в присваивании

переменной с объявлением

bool debug_on = false;

case 'd': debug_on = true;

значения true: break;

if ( debug_on )

В нашу программу может входить код следующего вида: display_state_elements( obj );

case 'v':

cout << program_name << "::"

<< program_version << endl;

Опция -v выводит номер версии программы и завершает исполнение: return 0;

Опция -h запрашивает информацию о синтаксисе запуска и завершает исполнение.

case 'h':

// break не нужен: usage() вызывает exit()

Вывод сообщения и выход из программы выполняется функцией usage(): usage();

Опция -o сигнализирует о том, что следующая строка содержит имя выходного файла. Аналогично опция -l говорит, что за ней указан максимальный размер. Как нам обработать эти ситуации?

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

//если ofi1e_on==true,

//следующий параметр - имя выходного файла bool ofi1e_on = false;

//если ofi1e_on==true,

//следующий параметр - максимальный размер

случаи, присвоим true переменным, отражающим внутреннее состояние: bool limit_on = false;

case 'l': limit_on = true; break;

case 'o': ofile_on = true;

Вот обработка опций -l и -o в нашей инструкции switch: break;

Встретив строку, не начинающуюся с дефиса, мы с помощью переменных состояния можем узнать ее содержание:

//обработаем имя выходного файла

//выключим ofile_on

}

else if ( limit_on ) { // если -l встречалась

//обработаем максимальный размер

//выключим limit_on

}else {

//обработаем имя входного файла

}

Если аргумент является именем выходного файла, сохраним это имя и выключим

if ( ofile_on ) { ofile_on = false; ofile = pchar;

ofile_on:

}

Если аргумент задает максимальный размер, мы должны преобразовать строку встроенного типа в представляемое ею число. Сделаем это с помощью стандартной функции atoi(), которая принимает строку в качестве аргумента и возвращает int (также существует функция atof(), возвращающая double). Для использования atoi() включим заголовочный файл ctype.h. Нужно проверить, что значение максимального

// int limit; else

if ( limit_on ) { limit_on = false; limit = atoi( pchar ); if ( limit < 0 ) {

cerr << program_name << "::"

<<program_version << " : error: "

<<"negative value for limit.\n\n";

usage( -2 );

}

размера неотрицательно и выключить limit_on:

}

Если обе переменных состояния равны false, у нас есть имя входного файла. Сохраним

else

его в векторе строк:

file_names.push_back( string( pchar ));

При обработке параметров командной строки важен способ реакции на неверные опции. Мы решили, что задание отрицательной величины в качестве максимального размера будет фатальной ошибкой. Это приемлемо или нет в зависимости от ситуации. Также можно распознать эту ситуацию как ошибочную, выдать предупреждение и использовать ноль или какое-либо другое значение по умолчанию.

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

prog - d dataOl

будет обработана:

prog -oout_file dataOl

(Оба случая мы оставим для упражнений в конце раздела.)

Вот полный текст нашей программы. (Мы добавили инструкции печати для трассировки выполнения.)

#include <string>

С++ для начинающих 356

#include <vector>

#include <ctype.h>

const char *const program_name = "comline";

const char *const program_version = "version 0.01 (08/07/97)";

inline void usage( int exit_value = 0 )

{

//печатает отформатированное сообщение о порядке вызова

//и завершает программу с кодом exit_value ...

cerr << "порядок вызова:\n"

<<program_name << " "

<<"[-d] [-h] [-v] \n\t"

<<"[-o output_file] [-l limit] \n\t"

<<"file_name\n\t[file_name [file_name [ ... ]]]\n\n"

<<"где [] указывает на необязательность опции:\n\n\t"

<<"-h: справка.\n\t\t"

<<"печать этого сообщения и выход\n\n\t"

<<"-v: версия.\n\t\t"

<<"печать информации о версии программы и выход\n\n\t"

<<"-d: отладка.\n\t\t включает отладочную печать\n\n\t"

<<"-l limit\n\t\t"

<<"limit должен быть неотрицательным целым числом\n\n\t"

<<"-o ofile\n\t\t"

<<"файл, в который выводится результат\n\t\t"

<<"по умолчанию результат записывается на стандартный вывод\n\n"

<<"file_name\n\t\t"

<<"имя подлежащего обработке файла\n\t\t"

<<"должно быть задано хотя бы одно имя --\n\t\t"

<<"но максимальное число не ограничено\n\n"

<<"примеры:\n\t\t"

<<"$command chapter7.doc\n\t\t"

<<"$command -d -l 1024 -o test_7_8 "

<<"chapter7.doc chapter8.doc\n\n";

exit( exit_value );

}

int main( int argc, char* argv[] )

{

bool debug_on = false; bool ofile_on = false; bool limit_on = false; int limit = -1; string ofile;

vector<string> file_names;

cout << "демонстрация обработки параметров в командной строке:\n" << "argc: " << argc << endl;

for ( int ix = 1; ix < argc; ++ix )

{

cout << "argv[ " << ix << " ]: " << argv[ ix ] << endl;

char *pchar = argv[ ix ]; switch ( pchar[ 0 ] )

{

case '-':

{

cout << "встретился \'-\'\n"; switch( pchar[ 1 ] )

{

case 'd':

cout << "встретилась -d: "

<< "отладочная печать включена\n";

debug_on = true; break;

case 'v':

cout << "встретилась -v: "