Урок 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-/* |
При повторном входе в рекурсивную функцию в памяти машины создаются копии всего набора локальных переменных этой функции, организуемые в виде стека.
Рекурсии, как правило, не предусматривают никаких механизмов защиты памяти, так что иногда стек обрабатываемых величин может переполняться. Возможные ошибки такого рода должен предотвращать сам программист.
Оставить комментарий