5 * 4 * Factorial(3)

5 * 4 * 3 * Factorial(2)

5 * 4 * 3 * 2 * Factorial(1)

5 * 4 * 3 * 2 * 1 = 120

В данном случае реализована так называемая нисходящаярекурсия: вызовfactorial(5)означает, что функцияfactorialвызывает себя раз за разом:factorial(4), factorial(3),… до тех пор, пока не будет достигнутатерминальнаяситуация – ситуация окончания рекурсии. При каждом вызове текущие вычисления откладываются, локальные переменные и адрес возврата остаются в стеке. Терминальная ситуацияfactorial = 1достигается приn = 1. При этом рекурсивный спуск заканчивается, начинается рекурсивный возврат изо всех вызванных в данный момент копий функции: начинает строиться ответn*factorial(n-1).Сохраненные локальные параметры выбираются из стека в обратной последовательности, а получаемые промежуточные результаты:1*1, 2*1, 3*2*1, 4*3*2*1, 5*4*3*2*1– передаются вызывающим функциям.

Рекурсивная функция, вычисляющая n-й член ряда Фибоначчи, может иметь вид:

Int fibo(int n)

{

if ((n == 1) || (n == 2))

return 1; // выход из рекурсии

else return fibo(n-2) + fibo(n-1);

}

Примеры:

1.Составить функцию, рекурсивно определяющую значение биномиального коэффициентапри0<m<nпо формулам:

= = 1, = +

Int binom(int m, int n)

{

if ((m == 0) || (m == n))

return 1; // выход из рекурсии

else return binom(m, n-1) + binom(m-1, n-1);

}

2.Составить функцию, рекурсивно определяющую максимальный элемент в заданной части целочисленного массиваvector_n, начиная сk-го и до n-го элемента:

Int max_element(int k, int n, int vector[])

{

Int temp;

if (k == n-1)

return a[n-1]

else

{

temp = max_element(k+1, n, vector[]);

if (a[k] > temp)

return a[k];

else return temp;

}

}

3.Составить функцию, реализующую рекурсивный алгоритмК.Хоарабыстрой сортировки массиваvector_n. Сравниваются элементы vector_iиvector_j, причемi=1, j=n-1. Еслиvector_i< vector_j, то эти элементы уже отсортированы по возрастанию, поэтому значениеправогоиндексауменьшаетсяна единицу, и алгоритм повторяется. Еслиvector_i > vector_j, то они меняются местами, останавливаетсяправыйиндекс, и начинает увеличиватьсялевый. Обмен значениями с изменением направления движения после каждого обмена продолжается до тех пор, пока левый и правый индексы не встретятся друг с другом:i = j. В этом случае элементvector_iбудет стоять на своем месте в массиве: слева от него стоят элементы меньше его, а справа – больше. После этого алгоритм рекурсивно повторяется для левой и правой частей массива:

Void quick_sort(int left, int right, int vector[])

{

int i, last;

if (left >= right) // в векторе меньше двух элементов

return;

swap(left, (left + right)/2, vector);

last= left;

for (i=left+1; i<=right; i++)

if (vector[i]<vector[left])

swap(++last, i, vector);

swap(left, last, vector);

quick_sort(left, last-1, vector);

quick_sort(last+1, right, vector);

}

Операцию перестановки i-го иj-го элементов массива можно оформить функцией:

void swap(int i, int j, int vector[])

{

int temp;

temp=vector[i];

vector[i]=vector[j];

vector[j]=temp;

}

Особенности рекурсии:

• использование рекурсивной формы организации алгоритма выглядит изящнее итерационной и дает более компактныйтекст программы,

• недостаткирекурсии состоят в следующем:

1. если глубина рекурсии велика, то программа будет требовать во время исполнения много памяти, что может привести к переполнению стека,

2. рекурсивные алгоритмы, как правило, выполняются более медленно,

• при рекурсивном программировании велика вероятность ошибок, вынуждающих программиста к перезагрузке компьютера.

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