Функции. Основные принципы структурной методологии. Принцип формальности. Принцип иерархического упорядочивания, страница 23

double  Rec_Fact_Dn (double, int, int);              //объявление функции (прототип)

main()

{ int i=50, n=i;

double Fact;

Fact= Rec_Fact (1.0, 1, n);                                 //вызов функции

cout <<i << “!  =  ” <<  Fact << endl;

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 по уровням рекурсии:

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

Пример 2. Третью форму рекурсивных подпрограмм рассмотрим на примере вывода на печать символов введенной строки ‘HELLO’ в обратном порядке:

#include <iostream.h>

#include <stdio.h>

void  Reverse ();              // прототип функции

main()

{ cout << “Input string:\n”;

Reverse();

cout << endl;

return 0;

}

void  Reverse ();             

{int ch; 

if (( ch= getchar())!=’\n’)                                    {Reverse(); putchar(ch);                                     }   }

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

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

Пример 3. Рекурсивная функция возведения вещественного числа Х в целую степень N>=0

Следующая программа содержит описание рекурсивной функции возведения вещественного числа Х в целую степень N>=0 за минимальное число операций умножения.

#include <iostream.h>

#include <conio.h>

#include <math.h> double rec_degree(double, 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));   if (n < 0) y = 1 / y; cout <<x  << “   ” << n << “  “   <<   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 – нечетное }

Пример 4. Рекурсивная функция печати числа в виде строки символов

Следующая программа содержит описание рекурсивной функции printd, которая вызывает себя, чтобы напечатать все старшие разряды заданного числа, а затем печатает цифру последнего разряда.