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

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

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

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

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

7.5. Рекурсия

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

unsigned long factorial( int val ) {

if ( val > 1 )

return val * factorial( val-1 ); return 1;

Рекурсия обрывается по достижении 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. Например, если будет решено изменить проверку на:

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

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

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

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

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

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

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