Алгоритмы реализации сложной рекурсии на языке программирования С++
Возможна чуть более сложная схема: функция A вызывает функцию B, а та в свою очередь вызывает A. Это называется сложной рекурсией. При этом оказывается, что описываемая первой процедура должна вызывать еще не описанную. Чтобы это было возможно, требуется использовать описание функции B до ее использования.
Пример: вычислить значение выражения:
#include <iostream>
using namespace std;
int pow(int, int); // описание сигнатуры
double calc(int x, int n)
{
return (double)pow(x, n) / n; // вызов функции pow
}
int pow(int x, int n)
{
if (n == 1) return x;
return x*calc(x, n - 1); // вызов функции calc
}
int main()
{
int n, x;
cout << "n = "; cin >> n;
cout << "x = "; cin >> x;
double a = calc(x, n); // вызов рекурсивной функции
cout << a;
cin.get(); cin.get();
return 0;
}
Результат выполнения:
n=2
x=3
4.5
Префиксная и постфиксная форма записи
Если процедура вызывает сама себя, то, по сути, это приводит к повторному выполнению содержащихся в ней инструкций, что аналогично работе цикла. При этом различают префиксную и постфиксную формы записи.
Рис. 1
Рекуррентные соотношения
Во многих случаях в основе рекурсии лежат рекуррентные соотношения.
Рекуррентное соотношение -- это соотношение вида:
выражающее каждый член последовательности an через p предыдущих членов.
Вычисление требуемого элемента последовательности будет состоять в повторяющемся обновлении значений этой последовательности.
Каждое такое обновление называется итерацией, а процесс повторения итераций - итерированием.
Рекурсия или итерирование
Итерация -- организация обработки данных, при которой действия повторяются многократно, не приводя при этом к вызовам самих себя (в отличие от рекурсии).
Рассмотрим вычисление факториала в виде итерационной и рекурсивной процедуры.
Рис. 2
Вызов функции влечет за собой некоторые дополнительные накладные расходы, связанные с передачей управления и аргументов в функцию, а также возвратом вычисленного значения. Поэтому итерационная процедура вычисления факториала будет несколько более быстрым решением. Чаще всего итерационные решения работают быстрее рекурсивных.
Любые рекурсивные процедуры и функции, содержащие всего один рекурсивный вызов самих себя, легко заменяются итерационными циклами.
Еще одним недостатком рекурсии является то, что ей может не хватать для работы стека. При каждом рекурсивном вызове в стеке сохраняется адрес возврата и передаваемые аргументы. Если рекурсивных вызовов слишком много, отведенный объем стека может быть превышен. (Например, рекурсивное вычисление факториала отрицательного числа).
Однако процедуры, вызывающие себя два и более раз чаще всего не имеют простого не рекурсивного аналога. В этом случае множество вызываемых процедур образует не цепочку, а целое дерево. Существуют широкие классы задач, когда вычислительный процесс должен быть организован именно таким образом. Как раз для них рекурсия будет наиболее простым и естественным способом решения. Кроме того, рекурсивные алгоритмы, как правило, намного проще с логической точки зрения, чем итерационные.
Стандартная библиотека математических функций.
Математические функции хранятся в стандартной библиотеке math.h. Аргументы большинства математических функций имеют тип double. Возвращаемое значение также имеет тип double.
Углы в тригонометрических функциях задаются в радианах. Основные математические функции стандартной библиотеки.
математический факториал итерация рекурсивный
Рис. 3