Рекурсивная функция вычисления факториала

Рекурсивное определение факториала:

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

}

}

Таблица трассировки данной программы по уровням рекурсии выглядит следующим образом:

Текущий уровень рекурсии	Рекурсивный спуск	Рекурсивный возврат
	Reverse;
	Ввод: ‘H’; ch!=’\n’; Reverse;	Вывод: ‘H’
	Ввод: ‘E’; ch!=’\n’; Reverse;	Вывод: ‘E’
	Ввод: ‘L’; ch!=’\n’; Reverse;	Вывод: ‘L’
	Ввод: ‘L’; ch!=’\n’; Reverse;	Вывод: ‘L’
	Ввод: ‘O’; ch!=’\n’; Reverse;	Вывод: ‘O’
	Ввод ‘\n’; ch ==’\n’;

Рекурсивная функция возведения вещественного числа Х в целую степень 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);

}

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: