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

#include <iostream.h>

#include <conio.h>

main ()

{ void PopeAndDoge1(); PopeAndDoge1();

getch();

return 0 ;

}

void PopeAndDoge1() {         

PopeAndDoge1(); cout << “ Y popa byla sobaka, on ee lubil.”<< endl;

cout << “ Ona s’ela kysok mjasa, on ee ubil.”<< endl; cout << “ poxoronil I nadpic napical:”<< endl;  }        

В конце концов, работа и той и другой программ приведет к переполнению стека и возникновению ошибки времени выполнения.

Рекурсивная задача разбивается на этапы. Для ее решения вызывается рекурсивная функция, которая знает, как решать только простейшую часть задачи – базовую задачу. Если эта функция вызывается для решения базовой задачи, то она просто вызывает результат. Если функция вызывается для выполнения более сложной задачи, то она делит эту задачу на две части: одну часть, которую функция умеет решать, и другую, которую функция решать не умеет. Чтобы сделать рекурсию выполнимой, последняя часть должна быть похожа на исходную задачу, но быть по сравнению с ней несколько проще или несколько меньше. Эта новая задача подобна исходной, поэтому функция вызывает новую копию самой себя, чтобы начать работать над меньшей проблемой. Это называется шагом рекурсии. Шаг рекурсии содержит ключевое слово return, так как в дальнейшем результат шага будет объединен с той частью задачи, которую функция умеет решать, и сформируется конечный результат, который будет передан в исходное место вызова, возможно в main.

Примеры

Пример 1. Рекурсивное определение факториала

n!  =  n(n-1)!, если n>0;

n!  =  1, если n=0.

Pассмотрим программу, выполняющую вычисление факториала на рекурсивном возврате.

#include <iostream.h>

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

main()

{ int i=50;

double Fact;

Fact= Rec_Fact_Up (i);             //вызов функции

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

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

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

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

Введем в рекурсивную функцию дополнительно два параметра: Mult – для выполнения на спуске операции умножения накапливаемого значения факториала на очередной множитель; m - для обеспечения независимости рекурсивной функции от имени конкретной глобальной переменной, то есть для повышения универсальности функции:

#include <iostream.h>