Сортировка пустой или одноэлементной картотеки тривиальна. В противном случае стопка карт произвольным образом разбивается на две непустые части, каждая из частей независимо сортируется, а затем обе сортированные стопки „смешиваются " (сливаются) в одну сортированную картотеку. Разумеется, для такого слияния нужно в свою очередь задать алгоритм. А именно, если одна из двух стопок пуста, то нужно взять вторую. В противном случае сравнивают первые карточки стопок по признаку сортировки. Ту из карточек, которая должна идти перед другой или одного с ней ранга, вынимают, остаток стопки сливают с другой стопкой и перед получившейся в результате слияния стопкой кладется вынутая карточка.
Этот пример демонстрирует иерархическую структуру: алгоритм сортировки основан на алгоритме слияния.
Упражнения.
1. Выполнить алгоритм слияния для двух непустых последовательностей уже отсортированных целых чисел. Например, для последовательности 2, 3, 5, 7, 11, 13, 17, 19 и 11, 13, 17, 19, 23, 29, 31.
2. Дана последовательность 18,6,12,42,94,55,44,67. Отсортируйте ее указанным методом.
E. Алгоритм вычисления значения дроби (a + b)/(a — Ь)
Сначала вычисляем (используя алгоритм сложения и вычитания) значения выражения а + Ъ и а — b (все равно, последовательно или одновременно, поскольку ситуация здесь совместная), а потом образуем частное от деления полученных результатов (используя алгоритм деления).
Здесь обнаруживается как иерархическое строение, так и совместность.
F. Алгоритм вычисления числа е (т. е. вычисления последовательности дробей — приближения для е)
Основание натуральных логарифмов е иррационально, поэтому его можно определить только с помощь бесконечной последовательности рациональных чисел, все лучше приближающие е. По Ламберту (1766 г.) такую последовательность можно получить следующим образом.
Начиная с 
последовательно вычислять
и образовать последовательность рациональных чисел 
.
Здесь речь идёт о незавершающемся алгоритме для вычисления вычислимого вещественного числа, опирающемся на алгоритм из пункта Е.
Упражнения.
1. Вычислите третье приближение к числу e, то есть величину 
.
2. Обдумайте правило останова для вычисления приближения к числу e с заданной точностью.
G. Алгоритм, распознающий, можно ли получить последовательность знаков a из последовательности знаков Ь посредством вычёркивания некоторых знаков
Если а — пустая последовательность знаков, то ответом будет «да». В противном случае нужно посмотреть, не пуста ли последовательность Ь. Если это так, то ответом будет «нет». Иначе нужно сравнить первый знак последовательности а с первым знаком последовательности Ь. Если они совпадают, то надо снова применить тот же алгоритм к остатку последовательности а и остатку последовательности Ь. В противно случае нужно снова применить тот же алгоритм к исходной последовательности а и остатку последовательности Ь.
Пример. Последовательность 001100 можно получить из последовательности 010101010, например, так: 010101010.
Это алгоритм выдаёт двузначный результат, «да» или «нет», т. е. он является алгоритмом распознавания свойства «быть частью данной последовательности знаков». Заметим, что распознавание того, является ли а (связным) подсловом b, — вещь более сложная.
Упражнение. Приведите нетривиальные примеры последовательностей, которые можно (нельзя) получить друг из друга.
В случаях C и D речь идет о недетерминистических и, вообще говоря, недетерминированных алгоритмах. Все другие являются примерами детерминистических алгоритмов, причем все, кроме F, завершающиеся.
Рекурсия и итерация
В последнем примере мы имеем наиболее простой случай: количество элементарных шагов обработки постоянно и не зависит от чисел а и b. Иначе обстоит дело в других примерах: в случае А это количество зависит от разрядности большего слагаемого, в случае B —от величины разлагаемого числа, в случаях C и D—от размера картотеки, а в случае F оно бесконечно. Хотя описание алгоритма конечно и постоянно, количество фактически выполняемых шагов — величина переменная; это оказывается возможным благодаря использованию приёма, сводящего общую задачу к „более простой" задаче того же класса. Этот трюк называю рекурсией. В примерах C и D наличие рекурсии очевидно из самого словесного описания алгоритма. В примерах A, B и G мы имеем специальный случай рекурсии — повторительную рекурсию. При словесном описании ее часто записывают, как например, в случае B, в форме итерации: «Пока выполнено определённое условие, повторяй...». В примере F речь идёт о безусловном (не зависящем от выполнения какого-либо условия) повторении.
Рекурсия — это широко распространённый метод, понятный без математической формализации, интуитивно близкий любому «человеку с улицы». Для рекурсии в ее наиболее общей, неитеративной форме типична необходимость отсрочки некоторых действий; см., в частности, пример D. По этой причине он вряд ли показан для забывчивых людей, но вполне пригоден для подходящим образом оборудованных машин. Повторение же — это в значительной степени наш повседневный опыт.
Наряд с рекурсией и повторением в алгоритмах встречается также разбор возможных случаев; см. G. Без разбора отдельных случаев, в частности, было бы невозможно окончание рекурсивных алгоритмов; см. C, D, G.