Информатика. 10 класс (Повышенный уровень)
Вспомогательный алгоритм — алгоритм, который можно использовать в других алгоритмах, указав его имя и, если необходимо, значения параметров. Вспомогательный алгоритм, записанный на языке программирования, называют подпрограммой.
Основные преимущества использования подпрограмм:
1. Разбиение комплексной программной задачи на простые шаги (декомпозиция). Это позволяет распределить решение одной задачи между различными людьми.
2. Уменьшение повторяющегося кода.
3. Многократное использование кода в других программах, в том числе и другими программистами.
4. Сокрытие деталей реализации от пользователей подпрограммы.
Подпрограммы, которые используются часто, объединяют в библиотеки. Большинство языков программирования позволяют не только использовать готовые подпрограммы, но и писать свои. В языке C++ подпрограммы оформляются в виде функций. Вам уже приходилось использовать различные функции, например из библиотеки cmath .
Перед тем как использовать функцию, ее нужно описать. Описание функции включает объявление и определение функции.
Объявление функции (пример 7.1) включает в себя заголовок функции, заканчивающийся точкой с запятой и включающий:
- имя функции f_N ;
- перечень формальных параметров с их типами
( type a_1, type a_2,… , type a_N ); - тип возвращаемого значения
r_type: r _type f_N (type a_1, type a_2, . type a_N);
Функции могут быть с параметрами или без параметров. Если функция не имеет параметров, то наличие круглых скобок после имени функции обязательно.
Определение функции состоит из заголовка функции (без точки с запятой) и тела функции, заключенного в фигурные скобки. В нем содержатся команды языка, реализующие вспомогательный алгоритм (пример 7.2).
Главная программа на С++ также реализована в виде функции. Эта функция всегда имеет имя main . Тип результата и наличие параметров этой функции может быть различными для различных сред программирования. В среде Code::Blocks функция main() имеет тип int и не имеет параметров.
Обычно объявление и описание подпрограмм размещают до функции main() . Если для решения задачи необходимо реализовать несколько функций, то нужно помнить о том, что функция должна быть объявлена до того, как она будет вызвана.
При вызове функции (пример 7.3) указывается ее имя и параметры, необходимые для вычислений. Эти параметры называют фактическими параметрами.
В описании функции задается список формальных параметров. Каждый параметр, описанный в этом списке, является локальным по отношению к описываемой функции, т. е. на него можно ссылаться по его имени из данной подпрограммы, но не из основной программы или другой функции.
Необходимость оптимизации программ по объему занимаемой памяти привела к появлению подпрограмм. Подпрограммы позволили не повторять в программе идентичные блоки кода, а описывать их однократно и вызывать по мере необходимости.
Использование подпрограмм позволяет повысить надежность кода программы. Подпрограммы обычно имеют небольшой размер, поэтому найти и исправить в них ошибки проще, нежели в большой программе.
Использование подпрограмм гарантирует относительную автономность модификации программы: если нужно что-либо изменить в программе, переделывать придется не всю программу, а только некоторые подпрограммы.
Пример 7.1. Объявление функций.
int kol _ cifr ( int n );
double plos_treug ( double a, double h );
Пример 7.2. Определение функции.
int kol_cifr ( int n )
while ( n > 0 ) <
double plos_treug ( double a, double h )
double s = a * h / 2 ;
return acos (- 1. );
В среде Dev-C++ функция main может иметь аргументы:
В среде Microsoft Visual Studio тип возвращаемого значения у функции main может быть void:
Пример 7.3. Вызов функции.
int k = kol _ cifr ( 12345 );
double s_kv = 2 * plos_treug ( a1, h1 );
В С++ объявление и определение функции может быть в разных местах. Объявление размещают до функции main , а определение после нее.
Рекурсия в алгоритме будет косвенной когда
// Test.cpp : Defines the entry point for the console application.
//
Compiling.
Test.cpp
C:\PROJECTS\Shelek\Recurce\Test\Test.cpp(8) : error C2065: 'B' : undeclared identifier
C:\PROJECTS\Shelek\Recurce\Test\Test.cpp(12) : error C2373: 'B' : redefinition; different type modifiers
Error executing cl.exe.
Test.exe — 2 error(s), 0 warning(s)
Возникает замкнутый круг: одна из процедур неизбежно должна вызвать другую, еще не описанную; перестановка процедур местами ничего не дает, поскольку проблема симметрична. К счастью, разорвать его весьма просто; в частности, для C++ достаточно лишь объявить процедуру B перед вызовом, не описывая ее тело:
// Test.cpp : Defines the entry point for the console application.
//
void B(void); // теперь A знает, как вызвать B
void A(void)
<
B();
>
- Часть выражения, заключенная в скобки, имеет приоритет над остальной частью, находящейся вне скобок, и вычисляется раньше нее.
- Скобки могу быть вложенными, при этом приоритет вложенных скобок выше, чем охватывающих.
- Операции умножения/деления имеют приоритет выше, чем операции сложения/вычитания.
- Операции с равным приоритетом выполняются по порядку, слева направо.
- 2 * 4 = 8
- 9 / 3 = 3
- 8 (п.1) + 3 (п.2) = 11
- 4 * 5 = 20
- 20 (п.4) / 2 = 10
- 11 (п.3) 10 (п.5) = 1
- Выражение представляет собой сумму слагаемых.
- Слагаемое представляет собой произведение сомножителей.
- Сомножитель представляет собой число.
- Если мы сначала перемножаем сомножители, а потом складываем слагаемые, причем тут рекурсия?
- Что делать, если в выражении встретилось подвыражение в скобках?
- Определить сам язык.
- Разработать его транслятор (в нашем случае интерпретатор).
- Исчезли метасимволы в виде угловых скобок, теперь нетерминалы выделяются курсивом (за что Науру огромное человеческое спасибо от всех, кто публикует статьи в HTML).
- Добавлены метасимволы в виде квадратных скобок "[" и "]". Элементы, заключенные в квадратные скобки, являются необязатель;ными, т.е. могут быть пропущены.
- Добавлены метасимволы в виде фигурных скобок "<" и ">". Элементы, заключенные в фигурные скобки, могут повторяться произвольное число раз (в том числе ни разу).
- Выражение представляет собой сумму слагаемых.
- Слагаемое представляет собой произведение сомножителей.
- Сомножитель представляет собой число либо выражение, заключенное в скобки.
- Десятичные цифры "0", "1", "2", "3", "4", "5", "6", "7", "8", "9".
- Разделитель дробной части — десятичную точку ".".
- Знаки арифметических операций — "+", "-", "*", "/".
- Круглые скобки для группировки подвыражений — "(" и ")".
- expr ::= item< op-add item >
- op-add ::= + | —
- item ::= factor< op-mul factor >
- op-mul ::= * | /
- factor ::= number | ( expr)
- number ::= int-part [ .fract-part ]
- int-part ::= digits
- fract-part ::= digits
- digits ::= digit< digit >
- digit ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
- Выражение представляет собой слагаемое, после которого может быть произвольное количество операций-типа-сложения, за каждой из которых следует слагаемое.
- Операция-типа-сложения может быть сложением либо вычитанием.
- Слагаемое представляет собой сомножитель, после которого может быть произвольное количество операций-типа-умножения, за каждой из которых следует сомножитель.
- Операция-типа-умножения может быть умножением либо делением.
- Сомножитель представляет собой либо число, либо выражение, заключенное в круглые скобки.
- В оставшихся правилах продукции содержится уже хорошо знакомое нам описание категории "число".
- Терминальные символы перечислены в разделе "Алфавит калькулятора".
- Нетерминальные символы перечислены слева от метасимвола "::=" в разделе "Синтаксис калькулятора".
- Правила продукции перечислены в разделе "Синтаксис калькулятора".
- Начальным символом нашей грамматики является метасимвол "выражение" ("expr").
CScanner::CScanner(const char *pc)
<
m_pCurrent = pc;
>
bool CScanner::IsEmpty(void) const
<
return !(*m_pCurrent);
>
char CScanner::Current(void) const
<
return *m_pCurrent;
>
void CScanner::MoveNext(void)
<
m_pCurrent++;
>
// ожидается конец строки
class CCalcEndOfLineExpErr: public CCalcError
<
private:
char cBadChar;
public:
CCalcEndOfLineExpErr(char c) < cBadChar = c; >
CCalcEndOfLineExpErr() <>
virtual const char * Reason(void) const < return "Calc - End of line expected"; >
const char BadChar(void) const < return cBadChar; >
>;
// ожидается цифра или открывающая круглая скобка
class CCalcDigitOrOpenExpErr: public CCalcError
<
private:
char cBadChar;
public:
CCalcDigitOrOpenExpErr(char c) < cBadChar = c; >
CCalcDigitOrOpenExpErr() <>
virtual const char * Reason(void) const < return "Calc - Digit or '(' expected"; >
const char BadChar(void) const < return cBadChar; >
>;
// ожидается цифра
class CCalcDigitExpErr: public CCalcError
public:
CCalcDigitExpErr(char c) < cBadChar = c; >
CCalcDigitExpErr() <>
virtual const char * Reason(void) const < return "Calc - Digit expected"; >
const char BadChar(void) const < return cBadChar; >
>;
// ожидается открывающая круглая скобка
class CCalcCloseExpErr: public CCalcError
<
private:
char cBadChar;
public:
CCalcCloseExpErr(char c) < cBadChar = c; >
CCalcCloseExpErr() <>
virtual const char * Reason(void) const < return "Calc - ')' expected"; >
const char BadChar(void) const < return cBadChar; >
>;
// буфер строки пуст
class CCalcBufEmptyErr: public CCalcError
// деление на нуль
class CCalcDivByZeroErr: public CCalcError
extern double GetValue(CScanner &b); // возвращает значение выражения
// вспомогательная функция — преобразование литеры в число
int CharToInt(const char c)
<
// проверяем, является ли литера цифрой
if (!isdigit(c)) // если нет, вызываем исключение
throw CCalcDigitExpErr(c);
// цифра — вычисляем значение
return (c — '0');
> // CharToInt
// обработка числа
double GetNumber(CScanner &b)
<
// проверяем, не пуст ли буфер
if (b.IsEmpty())
throw CCalcBufEmptyErr();
// проверяем, является ли текущая литера цифрой
if (!isdigit(b.Current()))
throw CCalcDigitExpErr(b.Current());
// все в порядке — как и ожидалось, в буфере число
double resultValue = 0.0;
// считываем целую часть числа
while (isdigit(b.Current()))
<
resultValue *= 10.0;
resultValue += CharToInt(b.Current());
b.MoveNext();
> // while
// проверяем наличие необязательной дробной части
if (b.Current() == '.')
<
// пропускаем десятичную точку
b.MoveNext();
// считываем дробную часть
// сначала убедимся, что после точки следует цифра
if (!isdigit(b.Current()))
throw CCalcDigitExpErr(b.Current());
double step = 1.0;
while (isdigit(b.Current()))
<
step /= 10.0;
resultValue += step * CharToInt(b.Current());
b.MoveNext();
> // while
> // if
// возвращаем значение считанного числа
return resultValue;
> // GetNumber
/*
А теперь приступаем к первой функции, задействованной
в цепочке взаимной рекурсии.
Поскольку сомножитель может быть выражением, а функция разбора
выражения будет описана позже, в этом месте необходимо включить
предварительное описание функции GetExpr (без реализации), чтобы избежать
ошибки обращения к неопределенной функции при компиляции программы.
*/
double GetExpr(CScanner &b);
<
// обработка сомножителя
double GetFactor(CScanner &b)
<
// сомножитель может быть числом,
if (isdigit(b.Current())) // в этом случае его значение = значению этого числа,
return GetNumber(b);
// либо выражением в скобках, в этом случае его следует вычислить
else if (b.Current() == '(')
<
// пропускаем открывающую скобку
b.MoveNext();
// получаем значение выражения
double resultValue = GetExpr(b);
// проверяем наличие закрывающей скобки
if (b.Current() != ')')
throw CCalcCloseExpErr(b.Current());
// пропускаем закрывающую скобку
b.MoveNext();
// возвращаем значение сомножителя
return resultValue;
> // else if
else // текущий символ — не число и не открывающая скобка
throw CCalcDigitOrOpenExpErr(b.Current());
> // GetFactor
// обработка слагаемого
double GetItem(CScanner &b)
<
// получаем первый сомножитель
double resultValue = GetFactor(b);
Программирование рекурсивных алгоритмов на языке С++
Подпрограмма — поименованная или иным образом идентифицированная часть компьютерной программы, содержащая описание определённого набора действий. Подпрограмма может быть многократно вызвана из разных частей программы.
Назначение подпрограмм [ править ]
Выделение набора действий в подпрограмму и вызов её по мере необходимости позволяет логически выделить целостную подзадачу, имеющую типовое решение. Такое действие имеет ещё одно (помимо экономии памяти) преимущество перед повторением однотипных действий: любое изменение (исправление ошибки, оптимизация, расширение функциональности), сделанное в подпрограмме, автоматически отражается на всех её вызовах, в то время как при дублировании каждое изменение необходимо вносить в каждое вхождение изменяемого кода.
Даже в тех случаях, когда в подпрограмму выделяется однократно производимый набор действий, это оправдано, так как позволяет сократить размеры целостных блоков кода, составляющих программу, то есть сделать программу более понятной и обозримой.
В простейшем случае (в ассемблерах) подпрограмма представляет собой последовательность команд (операторов), отдельную от основной части программы и имеющую в конце специальную команду выхода из подпрограммы. Обычно подпрограмма имеет имя, по которому её можно вызвать, хотя ряд языков программирования допускает использование и неименованных подпрограмм. В языках высокого уровня описание подпрограммы обычно состоит по меньшей мере из двух частей: заголовка и тела. Заголовок подпрограммы описывает её имя и, возможно, параметры, то есть содержит информацию, необходимую для вызова подпрограммы. Тело — набор операторов, который будет выполнен всякий раз, когда подпрограмма будет вызвана.
Вызов подпрограммы выполняется с помощью команды вызова, включающей в себя имя подпрограммы. В большинстве современных языков программирования команда вызова представляет собой просто имя вызываемой подпрограммы, за которым могут следовать фактические параметры.
Виды подпрограмм. [ править ]
Процедура — это любая подпрограмма, которая не является функцией.
Функция — это подпрограмма специального вида, которая, кроме получения параметров, выполнения действий и передачи результатов работы через параметры имеет ещё одну возможность — она может возвращать результат. Вызов функции является, с точки зрения языка программирования, выражением, он может использоваться в других выражениях или в качестве правой части присваивания.
Подпрограммы, входящие в состав классов в объектных языках программирования, обычно называются методами. Этим термином называют любые подпрограммы-члены класса, как функции, так и процедуры; когда требуется уточнение, говорят о методах-процедурах или методах-функциях.
Оформление подпрограмм в С++ [ править ]
В языке С++ подпрограммы реализованы в виде функций. Функция принимает параметры и возвращает единственное скалярное значение. Как известно, программа на С++ состоит из одной или нескольких функций. Функция должна быть описана перед своим использованием.
Описание функции состоит из заголовка и тела функции.
Заголовок_функции
<
тело_функции
>
Заголовок функции имеет вид: type имя_функции ([список параметров])
type – тип возвращаемого функцией значения; Тип функции показывает, какое значение возвращает функция: целое, вещественное, строковое и так далее. Если тип функции не указан, то подразумевается, что функция возвращает целое значение типа int.
список параметров – список параметров (аргументов) содержит перечень типов и имен величин, разделенных запятыми, и заключенных в скобки. Если функция не имеет параметров, то скобки все равно необходимы, хотя в них ничего не указывается, то есть в скобках в этом случае будет пустое место. Например:
fun1(int a, int b, float d);
В случае, если вызываемые функции определены до функции main,структура программы будет такой.
Тип_результата f1(Список_переменных)
<
Операторы
>
Тип_результата f2(Список_переменных)
<
Операторы
>
.
Тип_результата fn(Список_переменных)
<
Операторы
>
int main(Список_переменных)
<
Операторы основной функции, среди которых могут операторы вызова функций f1, f2, . fn
>
В случае, если вызываемые функции определены после функции main или даже в другом файле,необходимо до первого вызова функции сообщить программе тип возвращаемого функцией значения, а также количество и типы ее аргументов.
Рекурсия и ее виды [ править ]
Рекурсия — метод определения класса объектов или методов предварительным заданием одного или нескольких (обычно простых) его базовых случаев или методов, а затем заданием на их основе правила построения определяемого класса, ссылающегося прямо или косвенно на эти базовые случаи.
Другими словами, рекурсия — способ общего определения объекта или действия через себя, с использованием ранее заданных частных определений. Рекурсия используется, когда можно выделить само подобие задачи.
Рекурсивный алгоритм (процедура, функция):
- алгоритм называется рекурсивным, если в его определении содержится прямой или косвенный вызов этого же алгоритма;
- рекурсивная функция — одно из математических уточнений интуитивного понятия вычислимой функции.
Рекурсивная ветвь — алгоритм, который благодаря рекурсивности учитывает те или иные индивидуальные характеристики решаемой задачи из области своего определения.
Терминальная ветвь рекурсии — это предложение, определяющее некую начальную ситуацию или ситуацию в момент прекращения. Как правило, в этом предложении записывается некий простейший случай, при котором ответ получается сразу, даже без использования рекурсии.
Шаг рекурсии — это правило, в теле которого обязательно содержится, в качестве подцели, вызов определяемого предиката.
Основное правило рекурсии: до рекурсивного вызова должна стоять проверка на возврат из рекурсии.
Виды рекурсии [ править ]
Существуют следующие виды рекурсии:
Прямая рекурсия [ править ]
В данном случае функция r1( ) вызывает саму себя.
#include <iostream>
using namespace std;
void r1 (int a);
void r2 (int a);
void r3 (int a);
void r1(int a)
<
cout << «function r1» << endl;
if (a < 6)
r1(a+1);
>
int main ( )
<
r1 (0);
return NULL;
>
Косвенная рекурсия [ править ]
В данном случае функция r1( ) вызывает функцию r2( ), которая вызывает r3( ).
Функция r3( ) в свою очередь снова вызывает r1( ).
#include <iostream>
using namespace std;
void r1 (int a);
void r2 (int a);
void r3 (int a);
void r1(int a);
<
cout <<< «function r1» << endl;
if (a < 6)
r2(a+1);
>
void r2(int a)
<
cout << «function r2» << endl;
if (a < 6)
r3(a+1);
>
void r3(int a)
<
cout << «function r3» << endl;
if (a < 6)
r1(a+1);
>
int main ( )
<
r1 (0);
return NULL;
>
Бесконечная рекурсия [ править ]
Одна из самых больших опасностей рекурсии — бесконечный вызов функцией самой себя.
Например:
void function ()<
function(); >
int Function (unsigned int n)<
// Unsigned int — тип, содержащий неотрицательные значения
if (n > 0)
<
Function(n++);
return n;
>
else return 0;
>
При использовании подобных алгоритмов появляется ошибка, предупреждающая о переполнении стека. Причиной такой проблемы чаще всего является отсутствие базиса, либо других точек останова, так же неправильно заданные точки прерывания рекурсии
Описание рекурсивных алгоритмов [ править ]
Описание рекурсивного алгоритма происходит с помощью блок-схем.
Блок-схема — распространенный тип схем (графических моделей), описывающих алгоритмы или процессы, в которых отдельные шаги изображаются в виде блоков различной формы, соединенных между собой линиями.
Рекурсивные процедуры и функции [ править ]
Как процедура, так и функция — это часть программного кода, оформленная в виде подпрограммы, которую можно выполнять по ходу выполнения основной программы произвольное количество раз. Основное их отличие состоит в том, что функция должна в своем определении иметь описание ее результата (точнее, его типа), а также должна содержать операцию присваивания результату какого-то значения. В основной программе вызов функции напоминает математическую функцию и выглядит как R=F(a, b. ), где R — переменная, которой будет присвоен результат вычисления функции, F — имя функции, a, b . — список аргументов, он может отсутствовать, но скобки все равно должны быть. Кроме этого, в большинстве языков программирования в теле функции запрещено изменять значения аргументов. Типичный пример — библиотечная функция y=sin(x).
В процедуре определение результата, как такового, отсутствует, поэтому ее вызов выглядит как P(a,b. ), где P — название процедуры, a,b. — список аргументов, который может отсутствовать вместе со скобками. В процедурах разрешается изменять значения своих аргументов, т.е. они могут быть как входными, так и выходными.
Если сказать коротко, то функция используется в том случае, когда нужно вернуть какое-то значение, результат, который получаем в ходе работы алгоритма. Каждая рекурсивная функция должна включать в себя условие окончания рекурсии, иначе рекурсия будет бесконечной, что приведёт к аварийному завершению программы. Процедура предназначена для выполнения ряда команд и ничего не возвращает.
Пример рекурсивной функции: Вычислить сумму чисел в интервале, заданном вводимыми числами. Использовать рекурсивную функцию.
Решение. Условием окончания рекурсии станет ситуация, когда верх-няя граница на единицу больше нижней границы, то есть интервал задан двумя соседними целыми числами.
#include <iostream>
using namespace std;
int sum(int y, int x);
int main()
<
int a, b;
cout<< «Enter 1-st number: » <<endl;
cin>> a;
cout<< «Enter 2-st number: » <<endl;
cin>> b;
cout<< sum(b, a) <<endl;
return 0;
>
int sum(int y, int x)
<
int s = 0;
if ((y — 1) == x)
s = y + x;
else
s = y + sum(y — 1, x);
return s;
>
Пример рекурсивной процедуры: Составить рекурсивную процедуру нахождения n–го числа Фибоначи.
#include <iostream>
voidfibonacci( unsigned long int&mber, int count, unsigned long intprev = 0 ) <
if ( count > 1 ) <
number += prev;
fibonacci( number, count — 1, number — prev );
>
>
int main() <
unsigned long int fib = 1;
fibonacci( fib, 10 );
std::cout<< fib <<std::endl;
return 0;
>
Глоссарий [ править ]
Бесконечная рекурсия (на самом деле это условное обозначение так как при переполнении памяти компьютера программа выдаст ошибку и/или завершит ее в аварийном режиме).
Вызов подпрограммы выполняется с помощью команды вызова, включающей в себя имя подпрограммы. В большинстве современных языков программирования команда вызова представляет собой просто имя вызываемой подпрограммы, за которым могут следовать фактические параметры.
Косвенная рекурсия — При косвенной рекурсии имеется циклическая последовательность вызовов нескольких алгоритмов.
Подпрограмма — поименованная или иным образом идентифицированная часть компьютерной программы, содержащая описание определённого набора действий. Подпрограмма может быть многократно вызвана из разных частей программы.
Процедура — это любая подпрограмма, которая не является функцией.
Прямая рекурсия — непосредственный вызов алгоритма (функции, процедуры, метода) из текста самого метода.
Рекурсивная ветвь — алгоритм, который благодаря рекурсивности учитывает те или иные индивидуальные характеристики решаемой задачи из области своего определения.
Рекурсия — метод определения класса объектов или методов предварительным заданием одного или нескольких (обычно простых) его базовых случаев или методов, а затем заданием на их основе правила построения определяемого класса, ссылающегося прямо или косвенно на эти базовые случаи.
Тело подпрограммы — набор операторов, который будет выполнен всякий раз, когда подпрограмма будет вызвана.
Терминальная ветвь рекурсии — это предложение, определяющее некую начальную ситуацию или ситуацию в момент прекращения. Как правило, в этом предложении записывается некий простейший случай, при котором ответ получается сразу, даже без использования рекурсии.
Функция — это подпрограмма специального вида, которая, кроме получения параметров, выполнения действий и передачи результатов работы через параметры имеет ещё одну возможность — она может возвращать результат. Вызов функции является, с точки зрения языка программирования, выражением, он может использоваться в других выражениях или в качестве правой части присваивания.
Шаг рекурсии — это правило, в теле которого обязательно содержится, в качестве подцели, вызов определяемого предиката.
Прямая и косвенная рекурсия
Если подпрограмма P вызывает другую подпрограмму Q, которая, в свою очередь, прямо или косвенно вызывает Р, то Р называют косвенно рекурсивной.
procedure P; begin Q end;
procedure Q; begin P end;
Предварительное (опережающее) описание подпрограммы
При косвенной рекурсии две подпрограммы, например, P и Q, содержат взаимные вызовы друг друга. При компиляции процедуры P компилятор не может правильно обработать вызов процедуры Q, поскольку она описана ниже по тексту. Разрешить эту ситуацию позволяет предварительное (или опережающее) описание.
Предварительное описание – это заголовок подпрограммы, за которым следует ключевое слово forward вместо тела подпрограммы. Предварительное описание вызываемой процедуры Q дается раньше описания вызывающей процедуры P
procedure Q(список формальных параметров); forward; <Предварительное описание>
Опасности рекурсии
При применении рекурсивных алгоритмов следует избегать трех основных опасностей:
Бесконечной рекурсии.
Необоснованного применения рекурсии. Обычно это происходит, если алгоритм типа рекурсивного вычисления чисел Фибоначчи многократно вычисляет одни и те же промежуточные значения.
Глубокой рекурсии. Если алгоритм достигает слишком большой глубины рекурсии, он может привести к переполнению стека. Минимизировать использование стека можно за счет уменьшения числа определяемых в подпрограмме переменных, использования глобальных переменных. Если стек все равно переполняется, перепишите алгоритм в нерекурсивном виде.
Бесконечная рекурсия
Наиболее очевидная опасность рекурсии заключается в бесконечной рекурсии. Проще всего совершить эту ошибку, если просто забыть о проверке условия остановки рекурсии, как это сделано в нижеследующем примере:
<*>writeln(‘У попа была собака, …’);
begin PopAndDog end.
Теоретически программа будет бесконечно выводить всем известные строки (вывод на рекурсивном спуске). Однако, если в процедуре PopAndDog поменять местами оператор вывода и оператор вызова PopAndDog, то она ничего не выведет, хотя теоретически будет работать бесконечно. Это объясняется тем, что оператор вызова новой копии процедуры PopAndDog будет стоять ДО оператора writeln. Вывод будет на рекурсивном возврате, который никогда не произойдет из-за того, что рекурсивный вызов происходит безусловно.
В действительности из-за конечного размера памяти, выделяемой под стек вызовов подпрограмм, в конце концов произойдет переполнение этого стека и программа будет аварийно остановлена.
Для того чтобы работа рекурсивно вызванной подпрограммы когда-либо завершилась, необходимо, чтобы рекурсивное обращение к ней подчинялось некоторому условию, которое на каком-то уровне рекурсии становилось ложным, и нового вызова не происходило.
Добавим в процедуру PopAndDog параметр, который сначала равен максимальному числу рекурсивных вызовов, а при очередном рекурсивном вызове уменьшается на 1.
writeln(‘У попа была собака, …’);
if n>0 then PopAndDog(n-1)
После n вызовов значение n станет равным 0, и условие вызова перестанет выполняться.