Если из постановки задачи рекурсию извлечь не удаётся, то за счет перехода к её некоторому обобщению иногда это сделать можно. Как правило, это обобщение протекает за счет введения дополнительных параметров, то есть намеренного погружения или, по-другому, вложения исходной задачи в пространство большей размерности, чем это обусловлено её основными параметрами. Отсюда еще и такие названия данной опорной схемы: “Погрузить”, “Вложить”. Использование обсуждаемой схемы предполагает, что из решения обобщенной задачи без особого труда может быть получено решение исходной задачи. В некоторых случаях рассматриваемая схема может быть использована для улучшения быстродействия алгоритма или для перехода от одного типа рекурсии к другому. Заметим, что “Обобщение” является наиболее общей и часто используемой схемой при решении многих задач рекурсивными алгоритмами.

A. Разбиение целого на части. Составим рекурсивную программу-функцию подсчета количества x (m) разбиений натурального числа m, то есть его представлений в виде суммы натуральных чисел. Пусть, например, m=6. Тогда разбиениями m являются его представления в виде:

Таким образом, x (m)=11 и понятно, что простым перебором возможных случаев уже при m>10 справиться с задачей достаточно сложно. Для нахождения решения исходной задачи перейдем к рассмотрению обобщенной задачи. Составим программу-функцию подсчета количества P(m,n) разбиений натурального числа m со слагаемыми, не превосходящими n. Ясно, что x (m)=P(m,m). Поэтому достаточно научиться вычислять значения функции P(m,n). Но для неё нетрудно выделить рекурсивную базу и указать правило декомпозиции. Сделать это можно, исходя из следующих вполне прозрачных свойств этой функции.

1. P(m, 1) = 1 - существует только одно разбиение m, в котором слагаемые не превосходят единицы, а именно: m=1+1+…+1.

2. P(1, n) = 1 - число единица имеет только одно представление при любом n.

3. P(m, n) = P(m, m) при n>m - слагаемые, большие m, в разбиениях отсутствуют.

4. P(m, m) = P(m, m-1)+1 - существует лишь одно разбиение со слагаемым, равным m. Все иные разбиения имеют слагаемые, не превосходящие m-1.

5. P(m, n) = P(m, n-1) + P(m-n, n) (n<m). Обоснование этого соотношения проводится так. Все разбиения m на сумму слагаемых, не превосходящих n, можно разбить на два непересекающихся класса: суммы, не содержащие n в качестве слагаемого, и суммы, содержащие такое n. Количество элементов первого класса равно P(m, n-1), а количество элементов второго класса подсчитаем так. Без учета слагаемого n суммы элементов второго класса равны m-n. Значит, их общее количество равно P(m-n, n) и, следовательно, общее количество элементов второго класса также равно этой величине. Тем самым свойство 5 установлено.

Первые два свойства определяют базу рекурсии, а следующие три задают декомпозицию. Строго в соответствии с этими утверждениями и составлена рекурсивная программа-функция deco(n,m) для вычисления величины P(m,n):

Контрольные примеры:

B. Абракадабра. Последовательность из латинских букв строится следующим образом. На нулевом шаге она пуста. На каждом последующем шаге последовательность удваивается, то есть приписывается сама к себе, и к ней слева добавляется очередная буква алфавита (a, b, c, …). По заданному числу n определить символ, который стоит на n-м месте последовательности, получившейся после шага 26.

Эта задача предлагалась участникам областного тура Всероссийской олимпиады школьников по информатике в 1998 году. Приведем первые шаги формирования последовательности: 0 - пустая последовательность, 1 - a, 2 - baa, 3 - cbaabaa, 4 - dcbaabaacbaabaa, … . Мы имеем явно рекурсивный процесс. Построим более общую программу-функцию, чем это требуется по условиям задачи. Пусть abra(k,n) - n-я буква в последовательности, полученной на шаге k (k=1..26). Тогда ясно, что abra(k,1) равно k-й букве латинского алфавита. Этот факт можно взять в качестве базы рекурсии, а функцию для определения этой буквы записать так:

Декомпозицию удобно организовать по k, проводя “раскрутку” последовательности по шагам в обратном направлении. Это приводит к следующей функции:

Контрольные примеры:

abra(4, 6) = “b”,    abra(26, 4) = “w”,    abra(26, 2²⁶ - 127) = “g”.

C. Рекуррентная последовательность. Напишем программу вычисления функции fo(n), определенной для целых неотрицательных n следующим образом:

fo(2×n) = fo(n),    fo(2×n+1) = fo(n) + fo(n+1)    (n=1, 2, …).

Контрольные примеры:

Заметим, что вычисление fo(7777777777) занимает уже достаточно много времени. Происходит это по причине “двойного” рекурсивного обращения в последней строке программы. Улучшение быстродействия может быть достигнуто или введением динамической базы, при которой будут исключены повторные вычисления уже найденных значений функции, или переходом к более общей задаче. Остановимся на втором варианте. Рассмотрим вспомогательную функцию трех переменных:

Ясно, что fo(n) = gg(n, 1, 0). Кроме того, для gg(n, i, j) легко проверяется справедливость следующих рекуррентных формул:

Все эти соотношения вместе с определением функции gg(n, i, j) позволяют предложить для её вычисления такую рекурсивную функцию:

Контрольные примеры:

Стоит отметить, что вычисления по предложенной программе-функции gg(n, i, j) проводятся весьма эффективно и реализуются не более чем за élog₂(n)ù операций деления и 2×élog₂(n)ù операций сложения и вычитания.