Презентация на тему Рекурсивные алгоритмы (C++). Лекция 8 по основам программирования

включает аналогичные объекты в виде составных  частей.

и ранее определенные значения, а так же способ организации

вычислений, при котором функция вызывает сама себя с другим аргументом.
Простая рекурсия – вызов функции из неё же самой непосредственно.
Сложная, или косвенная рекурсия – вызов через другие функции, например, функция а вызывает функцию б, а функция б функцию а.

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

разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него.
Рекурсивно упорядочиваем подмассивы.

i,j,mode;
if (a>=b) return;
for (i=a, j=b, mode=1; i

j; mode >0 ? j-- : i++)
if (in[i] > in[j]) {
int c = in[i]; in[i] = in[j]; in[j]=c;
mode = -mode;
}
sort(in,a,i-1);
sort(in,i+1,b);
}

массив разбивается на две части примерно одинакового размера;
Каждая

из получившихся частей сортируется отдельно тем же самым алгоритмом;
Два упорядоченных массива половинного размера соединяются в один.

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

Эле­мен­ты

пе­ре­но­сим до тех пор, по­ка один из ис­ход­ных мас­си­вов не за­кон­чит­ся.

По­сле это­го остав­ший­ся «хвост» од­но­го из вход­ных мас­си­вов до­пи­сы­ва­ет­ся в ко­нец ре­зуль­ти­рую­ще­го мас­си­ва. 

Реализовать алгоритм сортировки рекурсивным слиянием списка.