Описание типа возвращаемого значения

Урок 9.5. Модификаторы типа функции

Читать далее

Урок 9.6. Рекурсивные функции

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

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

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

Применять рекурсивные методы программирования стоит в тех задачах, где рекурсия использована в определении обрабатываемых данных. Это, как правило, связано с такими динамическими структурами данных как стеки, деревья, очереди и др. Многие задачи, решаемые при помощи рекурсии, более эффективно решаются либо с помощью итеративных алгоритмов либо с помощью подпрограмм. Например, вычисление факториала, которое мы рассмотрим, удобно для объяснения рекурсии, однако не дает никакого выигрыша в программной реализации. Более того, рекурсивный алгоритм вычисления факториала работает медленнее итеративного алгоритма, за счет накладных расходов на вызов функции и возврат значений.

Рассмотрим пример программы вычисляющей факториал положительного числа.

#include <stdio.h>
#include <conio.h>
#include <iostream>
using namespace std;
void main()
{
   int f(int k); //функция вычисления факториала
   int fact = f(5);
   cout << "fact! = " << fact;
getch();
}
// Рекурсивная функция вычисления факториала
int f(int k)
{
if (k < 0)  return 0;
if (k == 0) return 1; //т.к. 0! == 1
return k * f(k-1);
}

При первом вызове f(5) функция возвращает выражение 5*f(4), т.е. функция f() фактически не возвращает значение, а вызывает сама себя с другим значением. Рекурсивные вызовы будут продолжаться до тех пор, пока k не станет равным 0. Будет создана следующая цепочка возвращаемых выражений:

5*f(4), 4*f(3), 3*f(2), 2*f(1), 1*f(0)

Вызов f(0)не провоцирует дальнейших вызовов, а возвращает значение 1, произведение 1*1 будет возвращено предыдущему вызову и т.д. до вызова f(5), которому возвращается значение 120. Тем самым будут организованы следующие умножения:

1*1*2*3*4*5, а в общем случае 1*1*2*3*4*5*…*(k-1)*k

Рассмотрим еще один традиционный пример функции, представленной в форме прямой рекурсии, – печать чисел как последовательности символов.

#include <stdio.h>
#include <conio.h>
 
void main()
{ void printd(int n); 
  int n;
  n = 135;
  printd(n);
_getch();
}
//Рекурсивная функция 
void printd(int n) // печать n
{ int i;
  if (n < 0) 
  {
     putchar('-'); // печать минуса для отрицательных чисел
     n=-n;
  }
  if ((i = n / 10)!= 0) printd(i);
  putchar(n%10+'0'); // преобразование цифры в символ
}

Рассмотрим работу этой функции для числа n=153. Поскольку число положительно, то операторы печати знака минус putchar('-'); и смена знака числа n=-n; пропускаются.

Оператор if ((i=n/10)!=0) printd(i); проверяет целую часть частного 153/10 = 15 на ноль. Если целая часть не ноль, то с этим значением (15) идет вновь обращение к функции printd(), а после возврата из нее оператором putchar(n%10+'0'); печатается остаток от деления 153%10 = 3, т.е. 3. Аналогично, вторая printd() передает третьей 1 (та печатает ее), а затем сама печатает 5.

Таким образом, однократное обращение извне к функции printd(); вызовет трехкратное ее срабатывание.

Задание на дом: напишите рекурсивную функцию вычисления целой степени вещественного числа.

Решение:

#include <stdio.h>
#include <conio.h>
#include <iostream>
 
using namespace std;
void main()
{  double power(double a, int n);//прототип функции
   double a = 5;
   int n = - 3;
 
   double d = power(a, n);
   cout << a << "^" << n << " = " << d; 
_getch(); 
} 
// Рекурсивная функция вычисления целой степени вещественного числа
double power(double a, int n)
{
   if (n == 0) return 1;
   if (a == 0) return 0;
   if (n > 0)  return a * power(a, n-1);
   if (n < 0)  return power(a, n+1) / a;
}

Задание на дом: напишите рекурсивную функцию вычисления суммы элементов вектора. Тело функции должно состоять из одной строчки.

Решение (2 варианта summa() и summa1()):

#include <stdio.h>
#include <conio.h>
#include <iostream>
using namespace std;
void main()
{
   double summa (int *v, int n); //прототипы функций
   double summa1(int *v, int n);
   int v[5] = {1, 2, 3, 4, 5};
   double s = summa(v, 5);
   cout << "s = " << s << endl;
   double s1 = summa1(v, 5);
   cout << "s1 = " << s1 << endl; 
_getch(); } 
// Рекурсивные функции вычисления суммы элементов вектора 
double summa(int *v, int n) 
{    
   return n > 0 ? summa(v, n-1) + v[n-1] : 0;
}
double summa1(int *v, int n)
{
   return n > 0 ? summa(v+1, n-1) + *v : 0;
}

Рассмотрим пример косвенной рекурсии. Пример принадлежит к классу алгоритмов, работающих с данными, структура которых тоже определяется рекурсивно. Характерной задачей такого рода является преобразование простых выражений в соответствующую постфиксную форму (иначе Полиз – польскую инверсную запись), т.е. в форму, при которой знак операции следует за операндами. Выражение будем определять в виде РБНФ[*] так:

Выражение = Слагаемое{("+" I "-")Слагаемое}.
Слагаемое = Множитель{("*" I "/")Множитель}.
Множитель = Буква I "("Выражение")" I "["Выражение"]"

Обозначая выражение как Е, слагаемые как Т1, Т2, а множители как F1, F2, запишем правила преобразования:

T1+T2 --> T1T2+
T1-T2 --> T1T2-
F1*F2 --> F1F2*
F1/F2 --> F1F2/
(E) --> E
[E] --> E
___________________________________________________________________
[*]
РБНФ - расширенная форма Бэкуса-Наура, метанотация (формализм) для записи синтаксических конструкций. В данном примере использованы такие метасимволы:.,+,{,},(,),I. Эти метасимволы читаются следующим образом:

  • А = ВС - синтаксическая конструкция А состоит из следущих друг за другом конструкций В и С.
  • А = В I С - А состоит либо из В, либо из С.
  • А = {B} - А может состоять из конкатенации любого числа (включая ноль) конструкций В.

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

#include <stdio.h>
#include <conio.h>
 
#define EOL 0x0a
char *ch = new char [100];
char *rez = new char [100];
char *rez1;
 
void Mnoj(); // множитель 
void Slag(); // слагаемое
void Vir();  // выражение
void main()
{
  rez1 = rez; //адрес rez будет меняться, а для вывода результата 
              //нужно начало строки
  scanf("%30s", ch); //не более 100 символов
  Vir();
  *rez = '\0'; 
  puts("rez1=");
  puts(rez1);
_getch();
}
 
void Vir() /* выражение */
{  char OpSl;
   Slag();
   while( (*ch == '+') || (*ch == '-')) 
       {
	 OpSl =* ch++; // операция сложения 
	 Slag();
	 *rez++ = OpSl;
       }
  //*rez = '\0';
} // конец выражения 
 
void Slag() /* слагаемое */
{  char OpUmn;
   Mnoj();
     while ((*ch == '*') || (*ch == '/')) 
	{
	   OpUmn =* ch++;
	   Mnoj();
	   *rez++ = OpUmn;
	}
}
 
void Mnoj() /* множитель */
{
   if (*ch == '(') 
	  { ch++; 
	    Vir();
	    while (*ch++ != ')'); 
	    return;
	   }
	else
	   if (*ch == '[') 
		  { ch++; 
		    Vir();
		    while (*ch != ']') ch++;
    	          }
	    else
		 while ((*ch < 'a') || (*ch > 'z'))
			ch++;
   *rez++ = *ch++;
} // конец множителя 
 
//Результат работы:
 >a+b          ab+
 >a*b+c        ab*c+
 >a+b*c        abc*+
 >a*(b/[c-d])  abcd-/*

 

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

Рекурсии, как правило, не предусматривают никаких механизмов защиты памяти, так что иногда стек обрабатываемых величин может переполняться. Возможные ошибки такого рода должен предотвращать сам программист.

 

Урок 9.4.6. Массивы в качестве аргументов

Читать далее

Урок 9.4. Аргументы функции

9.4.1. Передача аргументов и возврат значений
9.4.2. Передача аргументов по умолчанию
9.4.3. Указатели в качестве аргументов
9.4.4. Передача аргументов функции по ссылке
9.4.5. Функции в качестве аргументов других функций
9.4.6. Массивы в качестве аргументов
9.4.7. Аргументы функции main()

 

9.4.1. Передача аргументов и возврат значений

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

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

Определим функцию spaсe(), которая оставляет при печати задаваемое количество пробелов:

void space(int number)
{ int count;
  for(count=1;count<=number;count++)
  putchar(' ');
}
 
Приведем несколько примеров возможных вызовов этой функции:
 
space(25); // функция использует в качестве аргумента константу 
 
int spaces;
spaces=25;
space(spaces); // аргументом является переменная
 
//аргументом является выражение 
space((37-strlen("Examples of calls"))/2);

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

Возврат значения в вызывающую функцию осуществляется оператором return; или return(<выражение>);. Например, функция, которая вычисляет абсолютную величину числа, может быть описана так:

int abs(int x)
{
   if(x<0) x =- x;
   return(x);
}

Возвращаемое значение можно присвоить переменной или использовать как часть некоторого выражения. Например, y = abs(x); или y = 2*abs(x)+3;

 Задание. Перепишите функцию abs() так, чтобы ее тело состояло из одного оператора.

Значение выражения в return(<выражение>) всегда преобразуется к типу функции, и только после этого следует возврат.

Оператор return завершает выполнение вызываемой функции и передает управление вызывающей функции (оператору, следующему за вызовом). Это происходит даже в том случае, если оператор return является не последним оператором тела функции.

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

Управление возвращается в вызывающую функцию и в случае выхода по достижению конца функции. Значение при этом не передается.

Описание типа возвращаемого значения. Тип функции определяется типом возвращаемого ею значения, а не типом ее аргументов. Функция, которая не возвращает значения, должна быть описана как имеющая тип void. Например,

void ErrorMsg(char *s)/* функция не возвращает значения */
{

printf("==>%s\n",s);
}

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

9.4.2. Передача аргументов по умолчанию

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

Например:

void func(double m, char ch = ’*’, int i = 2);

Два параметра – ch и i имеют значения по умолчанию, которые будут использованы в случае вызова функции func с неполным списком параметров:
func(6.78, ’d’, 5);
func(6.78, ’d’);
func(6.78);

Вызов

func(6.78, 22);

будет неправильным, т.к. второй параметр должен иметь тип char.

При объявлении функции имена формальных параметров указывать необязательно, поэтому функцию можно объявит и так:

void func(double, char = ’*’, int = 2);

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

void f(double, char * = ”Hello”, int = 2);

если “забыть” пробел перед знаком =, то можно получить составную операцию умножения: *=;

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

9.4.3. Указатели в качестве аргументов

С помощью оператора return в вызывающую функцию можно передать только одну величину. А как вернуть две или более величины? Для этого нужно воспользоваться переменными типа указатель и передавать не данные, а их адреса или ссылки. Передача параметров по ссылке рассматривается в следующем разделе.

Пусть, например, мы хотим с помощью некоторой функции swap() выполнить обмен значений у переменных х и y. Ясно, что мы должны передать этой функции в качестве аргументов две величины и получить в качестве результата тоже две величины. Если мы определим функцию swap() таким образом:

void swap(int u, int v)
{  int temp;
   temp=u;
   u=v;
   v=temp;
}

и обратимся к ней с аргументами х,у: swap(x, y); то произойдет передача параметров по значению, т.е. переменная u получит значение из переменной х, а v – из переменной у, функция выполнит обмен значений над переменными u и v, которые существуют только в этой функции и вне её недоступны. Следовательно, в результате вызова swap(x, y) переменные х и у не изменяют своих значений.

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

void  swap(int *u, int *v) // u и v являются указателями 
{    int temp;
     temp = *u; // temp получает значение, на которое указывает u */
     *u = *v;
     *v = temp;
}
//Тогда вызов этой функции будет оформлен так:
int x,y;
swap(&x, &y); // передача адресов

Посмотрим, как работает теперь эта функция. В этом случае вместо передачи значений x и y мы передаем их адреса. Это значит, что формальные аргументы u и v при обращении будут заменены адресами, и, следовательно, они должны быть описаны как указатели. Поскольку x и y – целого типа, u и v являются указателями на переменную целого типа, и они описаны так: int *u,*v;

Далее рассмотрим оператор temp = *u;
Переменная temp целого типа и используется для временного хранения обмениваемых величин.

Значение переменной u – это &x (следует из вызова функции), поэтому переменная и является указателем на x. Значит, операция * и дает значение х. (Если бы мы написали temp = u;, то произошло бы запоминание адреса переменной x, а не ее значения.) Точно так же, желая присвоить переменной y значение переменной x, мы пользуемся оператором *u = *v; который соответствует оператору x = y ;

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

Обратите внимание! При вызове функции информация о переменной может передаваться функции в двух видах. Если мы используем форму обращения function1(x); происходит передача значений переменной x. Если же мы используем форму обращения function2(&x); происходит передача адреса переменной x. Первая форма обращения требует, чтобы определение функции включало в себя формальный аргумент того же типа, что и x: function1(int num);

Вторая форма обращения требует, чтобы определение функции включало в себя формальный аргумент, являющийся указателем на объект соответствующего типа: function2(int *ptr).

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

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

  • для передачи в функцию больших объемов (структур) данных, чтобы избежать копирования аргументов в стек;
  • для передачи в функцию аргументов, которые будут использованы не для передачи данных, а для возврата значений из функции, что позволяет вернуть из функции более одного значения;
  • для передачи в функцию адресов массивов (см. § 9.4.6. Массивы в качестве аргументов);


9.4.4. Передача аргументов функции по ссылке

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

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

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

void swap(int &u, int &v) // u и v являются ссылками 
{   int temp;
    temp=u;
    u=v;
    v=temp;
 }
//Тогда вызов этой функции будет оформлен так:
swap(a,b); //передача ссылок


9.4.5. Функции в качестве аргументов других функций

Рассмотрим пример, в котором имена функций, являющиеся по сути адресами функций, служат параметрами другой функции – функции fn_call(). В этой функции первый параметр является указателем на функцию.

#include <iostream>
#include <conio.h>
using namespace std;
double abs1(double x)
{
   return x >= 0.0 ? x : -x;
}
double abs2(double x)
{
   return x < 0.0 ? -x : x;
}
 
double fn_call(double (*f)(double), double x)
//параметр f имеет тип указатель на функцию
//с одним параметром типа double и возвращающую
//значение типа double
{  return f(x);
}
void main()
{
   cout << "x = " << fn_call(abs1,-2) << endl 
		  << "x = " << fn_call(abs2,-11);
   _getch();
}

Как видно из программы, функции abs1 и abs2 вызываются не напрямую, а через функцию fn_call, которой передаются имена (указатели) этих функций.

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

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

// Вариант для языка C (файл .c)
#include <stdio.h>
#include <conio.h>
 
 int swap();
 int example();
 int stringcmp();
 
 void main()
 { char *a = "aaaaysa1", *b = "aaaaysa";
   clrscr();
   printf("%s \n%s \n\n", a,b);
 
   //косвенные вызовы функций stringcmp и swap через функцию example
   if ( example(a,b,stringcmp ) > 0 )
           example(&a,&b,swap);
   printf("%s \n%s \n\n", a,b);
   getchar();
 }
 
 int example(char x[],char y[],int (*exch)())
 //exch - указатель на функцию, возвращающей целое значение*/
 {
   return(exch(x,y));
   //return((*exch)(x,y));
 }
 
 int stringcmp(char *s, char *t)
 // возвращает <0,если s < t;  
 //             0,если s = t;  
 //            >0,если s > t
 {
 for(;*s == *t && *s!=0 && *t!= 0; s++,t++);
 return(*s-*t);
 }
 
 int swap(char **pa, char **pb)
//меняет местами значения указателей
 {   char *temp;
     temp = *pa;
     *pa = *pb;
     *pb = temp;
 }
 
// Вариант для языка CPP (файл .cpp):
#include <stdio.h>
#include <conio.h>
 int swap(char **px, char **py);
 int example(char x[], char y[], int (*exch)(char *s, char *t));
 int stringcmp(char *s, char *t);
 typedef int FPT (char *s, char *);
 
 void main()
 {
    clrscr();
    char *a = "sssbb", *b = "sssa";
 
    printf("\nDo\n");
    printf("%s\n%s\n",a,b);
    if ( example(a,b,stringcmp ) > 0 )
       //example(&a,&b,(FPT)swap);
         swap(&a, &b);
 
    printf("\nPosle\n");
    printf("%s\n%s\n",a,b);
 getchar();
 }
 
int example(char x[],char y[],int (*exch)(char *s, char *t ))
            //exch - указатель на функцию, возвращающей целое значение
 {   return(exch(x,y));
   //return((*exch)(x,y));
 }
 
int stringcmp(char *s, char *t)
// возвращает <0, если s < t; 
//             0, если s = t; 
//            >0, если s > t
 {
  for(;*s == *t && *s != 0 && *t != 0; s++,t++);
  return(*s - *t);
 }
 
 int swap(char **pa, char **pb)
 //меняет местами значения указателей
 {  char *temp;
     temp =* pa;
     *pa =* pb;
     *pb = temp;
 }

Описание int(*exch)(); говорит о том, что exch – указатель на функцию, вызывающую целое значение. Первая пара скобок необходима, без них int *exch(); означало бы, что exch – функция, возвращающая ссылку на целое значение, а это совершенно разные вещи.

9.4.6. Массивы в качестве аргументов

9.4.7. Аргументы функции main()

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

Аргументы в командной строке являются дополнительными элементами в той же самой строке. Аргументы передаются функции main().

Компилятор Си предполагает наличие у main() трех аргументов. Первый аргумент – количество символьных строк, разделенных пробелами, в командной строке. Обычно, но не обязательно, этот аргумент типа int называется argc (от слов ARGument Count). Второй аргумент является массивом указателей символьных строк. Каждой символьной строке, входящей в командную строку, присваивается собственный указатель.

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

Ниже приводится пример передачи программе аргументов из командной строки. В командной строке было набрано:

>C:\BC\OUTPUT\exemain.exe str1 str2

main(int argcnt, char *argv[], char *envpr[]) 
// программа печати аргументов главной программы
// argcnt;  – количество аргументов 
// *argv[]; – массив указателей на аргументы 
// *envpr[];– массив указателей на строки, определяющие операционную среду 
{ int i;
  printf("Количество аргументов: %d \n", argcnt);
 
  for(i=0; i < argcnt; i++)
     printf("Аргумент %d %s \n",i, argv[i]);
 
  printf("\nОперационная среда:");
  while(*envpr)
     printf("\n%s",*envpr++);
 }
 
/*Результат работы программы:*/
Количество аргументов: 3
Аргумент 0 C:\TC\OUTPUT\EXMAIN.EXE
Аргумент 1 str1
Аргумент 2 str2
 
Операционная среда:
COMSPEC=C:\COMMAND.COM
PROMPT=$p$g
PATH=C:\;C:\SYS;C:\DOS;C:\TC;C:\MASM;C:\NC;C:\DOS\ALLARC;
NC=c:\nc

 

Урок 9.3. Вызов функции

Читать далее

Translate Переводчик

Подписка на новости

SmartResponder.ru
Ваш e-mail: *
Ваше имя: *

Хостинг для Wordpress сайтов