Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







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





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

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 по уровням рекурсии выглядит следующим образом:

Текущий уровень рекурсии Рекурсивный спуск Рекурсивный возврат
Rec_Fact_Up(5) n==5 Вывод n! == 120
Mult=Rec_Fact_Up(4); n==4 Mult * 5 = =120;
Mult=Rec_Fact_Up(3); n==3 Mult * 4 == 24;
Mult=Rec_Fact_Up(2); n==2 Mult * 3 == 6;
Mult=Rec_Fact_Up(1); n==1 Mult * 2 == 2;
Mult=1; Mult==1;

 

 

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

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

Введем в рекурсивную функцию дополнительно два параметра: 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 по уровням рекурсии:

 

Текущий уровень рекурсии Рекурсивный спуск Рекурсивный возврат
Rec_Fact_Dn(1.0,1,5);   Вывод n! = 120
Mult= Mult *1 =1; i ==1; Rec_Fact_Dn(1.0,2,5); Mult*5= 120;
Mult= Mult *2 = 2; i ==2; Rec_Fact_Dn(2.0,3,5); Mult*5= 120;
Mult= Mult *3 =6; i ==3; Rec_Fact_Dn(6.0,4,5); Mult*5= 120;
Mult= Mult*4 =24; i ==4; Rec_Fact_Dn(24.0,5,5); Mult*5= 120;
Mult= Mult*5= 120; i==5; Rec_Fact_Dn=120.0; Mult*5= 120;

 

Рекурсивная функция вывода на печать символов строки в обратном порядке

Рассмотрим вывод на печать символов введенной строки ‘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);

}

 









Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

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





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


©2015- 2021 zdamsam.ru Размещенные материалы защищены законодательством РФ.