Double T (unsigned n, double x)

Else

If (P)

Double Pow (double D, unsigned P)

Double Pow (double D, unsigned P)

Рекурсивное использование функций

Функции внутри своего тела могут вызывать сами себя. Такой вызов называется рекурсией. На основе рекурсии можно строить очень интересные алгоритмы обработки данных.

Рассмотрим функцию возведения вещественного значения D в целую положительную степень P. Очевидная реализация этой функции основана на использовании цикла:

{

double R = 1;

for (unsigned I = 0; I < P; ++ I)

R *= D;

return R;

}

А вот та же самая функция, реализованная на основе рекурсии:

{

return Pow (D, P – 1) * D;

return 1;

}

Основанием для рекурсии в этом примере послужило следующее рекуррентное соотношение:

приP = 0 приP > 0

Более сложный пример рекурсии основан на следующем рекуррентном соотношении (обычная реализация этого примера приведена в разделе 5.1 конспекта):

приn = 0 приn = 1 приn ≥ 2

Через рекурсию это рекуррентное соотношение реализуется так:

{

switch (n)

{

case 0:

return 1;

case 1:

return x;

default:

return 2 * x * T (n - 1, x) - T (n - 2, x);

}

}

Как видно из этих примеров алгоритм, реализуемый через рекурсию, выглядит более компактным и понятным по сравнению с обычной реализацией. С точки зрения эффективности, реализацию этих примеров через рекурсию вряд ли можно считать более эффективной, чем обычную реализацию. Это объясняется дополнительными затратами времени на многократный вызов функций и дополнительными затратами памяти (стека) на передачу аргументов.

Однако в ряде случаев использование рекурсии позволяет достичь существенного положительного эффекта.

Рассмотрим следующий пример: необходимо написать функцию для вычисления биномиальных коэффициентов:

n >= 0, 0 <= m <= n.

Значение биномиального коэффициента определяет число различных вариантов выбора m объектов из n объектов (как говорят, число сочетаний из n по m).

Основные свойства биномиальных коэффициентов:

Максимальное значение биномиального коэффициента достигается при m = n / 2.

Очевидная реализация функции основана на использовании циклов для вычисления числителя и знаменателя биномиального коэффициента и нахождения частного от их деления:

unsigned C(int n, int m)

{

if (m > n / 2)

m = n - m;

unsigned a = 1, b = 1;

for (int i = n; i >= n - m + 1; -- i)

a *= i;

for (int i = 1; i <= m; ++ i)

b *= i;

return a / b;

}

Нетрудно заметить, что этот алгоритм быстро приводит к выходу значений числителя или знаменателя за пределы диапазона значений типа данных unsigned. И действительно, эксперименты с этим вариантом функции показывают, что точное вычисление биномиальных коэффициентов возможно только при n < 17.

Найдем следующее соотношение:

.

То есть:

.

Тогда справедливо следующее рекуррентное соотношение, позволяющее вычислять очередное значение биномиального коэффициента через его предыдущее значение:

приm = 0 приm > 0

Это рекуррентное соотношение реализуется с помощью следующей рекурсивной функции:

unsigned int C(unsigned int n, unsigned int m)

{

if (m > n / 2)

m = n - m;

if (m == 0)

return 1;