ВУЗ:
Составители:
Рубрика:
22
III шаг.
I фаза.
A: 7 11 13 17 19 21 23 29 31 37 57 59 61 67
B: 2 5 43 67
II фаза.
C: 2 5 7 11 13 17 19 21 23 29 31 37 43 57 59 61 67 67
Разбиение на серии не обязательно проводить специально – это можно делать
в процессе слияния. Очевидно, серия заканчивается, если следующий элемент ли-
бо отсутствует, либо меньше предыдущего. Заметим также, что для сортировки
нам потребовалось всего 3 шага, несмотря на то, что исходная последователь-
ность состоит из 18 элементов,
а не из 8, как в предыдущем пункте.
2 Рекурсия
2.1 Основные определения
Рекурсия – это способ определения объекта, при котором он частично опре-
деляется через такой же объект. Определение, содержащее рекурсию, называется
рекурсивным
определением. Например, натуральное число – это либо 1, либо целое число, сле-
дующее за натуральным.
Рекурсивные определения удобно записывать с помощью форм Бэкуса-
Наура:
Массив ::= <пусто>
| элемент Массив
СписокПараметров ::= параметр
| СписокПараметров
’,’ параметр
Обратим внимание, что во всех предыдущих примерах объект при некотором
условии определяется нерекурсивно. Это условие является признаком окончания
рекурсии. Обратим также внимание, что рекурсивный объект может стоять как в
начале рекурсивного определения (леворекурсивное определение), так и в конце
(праворекурсивное определение).
Рекурсивно можно определять не только объекты, но
и математические
функции. Функция называется рекурсивной, если ее значение при некоторых зна-
чениях аргументов определяется через значение этой функции при других значе-
ниях аргументов. Например:
⎩
⎨
⎧
=
>−⋅
=
.0åñëè,1
,0åñëè,)!1(
!
n
nnn
n
⎩
⎨
⎧
=
>⋅
=
−
.0åñëè,1
,0åñëè,
1
n
naa
a
n
n
Страницы
- « первая
- ‹ предыдущая
- …
- 18
- 19
- 20
- 21
- 22
- …
- следующая ›
- последняя »
