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

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

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