Урок 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. Аргументы функции
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 |