|
|
Рекурсивная функция вычисления факториалаРекурсивное определение факториала: n! = n(n-1)!, если n>0; n! = 1, если n=0.
Pассмотрим программу, выполняющую вычисление факториала (5!) на рекурсивном возврате. double Rec_Fact_Up (int); // прототип функции int main() { int i=5; double Fact; Fact= Rec_Fact_Up (i); //вызов функции cout << i << "!= " << Fact << endl; _getch(); return 0; } double Rec_Fact_Up (int n) //определение функции { if (n<=1) return 1.0; else return Rec_Fact_Up(n-1) * n; //вычисление на рекурсивном возврате //можно представить состоящим из двух действий // Mult=Rec_Fact_Up(n-1) – непосредственно рекурсивный вызов; // Mult *n – оператор накопления факториала }
Таблица трассировки программы Rec_Fact_Up по уровням рекурсии выглядит следующим образом:
Многие задачи (в том числе и вычисление факториала) безразличны к форме используемой рекурсивной подпрограммы, однако есть классы задач, при решении которых программисту требуется сознательно управлять ходом работы рекурсивных функций. Рассмотрим выполнение действий на рекурсивном спуске на примере все того же алгоритма вычисления факториала. Введем в рекурсивную функцию дополнительно два параметра: Mult – для выполнения на спуске операции умножения накапливаемого значения факториала на очередной множитель; m - для обеспечения независимости рекурсивной функции от имени конкретной глобальной переменной, то есть для повышения универсальности функции:
double Rec_Fact_Dn (double, int, int); // прототип функции int main() { int i=5, n=i; double Fact; Fact= Rec_Fact_Dn (1.0, 1, n); //вызов функции cout <<i << "! = " << Fact << endl; _getch(); return 0; }
double Rec_Fact_Dn(double Mult, int i, int m) //определение функции { Mult=Mult*i; if (i==m) return Mult; else return Rec_Fact_Dn (Mult, i+1, m); }
Таблица трассировки значений параметров рекурсивной функции Rec_Fact_Dn по уровням рекурсии:
Рекурсивная функция вывода на печать символов строки в обратном порядке Рассмотрим вывод на печать символов введенной строки ‘HELLO’ в обратном порядке: void Reverse (); // прототип функции int main() { cout << "Input string:\n"; Reverse(); cout << endl; _getch(); return 0; } void Reverse () {int ch; if ((ch= getchar())!='\n') {Reverse(); putchar(ch); } } Таблица трассировки данной программы по уровням рекурсии выглядит следующим образом:
Рекурсивная функция возведения вещественного числа Х в целую степень N>=0 Программа реализует алгоритм возведения вещественного числа Х в целую степень N>=0 за минимальное число операций умножения:
double rec_degree(double, int); int main () { double x, y; int n; cout << " Input (X<= 10) Input (-90<=N<=-90)?: " << endl; cin >> x >> n; y=rec_degree(x, abs(n)); cout <<x << " " << n << " " << (n>0? y: 1/y) << endl; _getch(); return 0; }
double rec_degree(double x, int n) { double r; if (!n) return 1; //действия выполняются на рекурсивном возврате if (!(n% 2)) return r=rec_degree(x, n/2), r*r; //n – четное else return x *rec_degree(x, n-1); //n – нечетное }
Рекурсивная функция печати числа в виде строки символов Рекурсивная функция printd вызывает себя, чтобы напечатать все старшие разряды заданного числа, а затем печатает цифру последнего разряда. void printd (int); int main () { int a=12345; printd(a); cout << endl; _getch(); return 0; } void printd (int n) { if (n < 0) {putchar ('-'); n=-n; } if (n) {printd (n/10); //действия выполняются на рекурсивном возврате putchar (n%10 +'0'); } }
Вычисление НОД через итерации и через рекурсивную функцию int NOD_iter (int, int); int NOD_rec (int, int); int main () { int m=32, n=16; cout << m <<" " << n << " " << NOD_iter (m, n) << endl; cout << m <<" " << n << " " << NOD_rec (m, n) << endl; _getch(); return 0; }
int NOD_iter (int m, int n) { int r; do {r= m % n; m=n; n=r; }while (r); return m; }
int NOD_rec (int m, int n) { if (!(m % n)) return n; //действия выполняются на рекурсивном спуске else return NOD_rec(n, m %n); }
  ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...  Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...  Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...  Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
Вывод: ‘H’