Возможности получения рекурсии

Нет готовых рецептов, как для данной произвольной проблемы получить (рекурсивный) алгоритм ее решения. Однако есть некоторые рекомендации.

1) органически рекурсивные определения

Некоторые рекурсивные функции являются точным "слепком" с соответствующего определения (вспомните определение факториала числа).

2) извлечение рекурсии из постановки задачи

В большинстве случаев, однако, решаемая задача не является алгоритмически сформулированной. Поэтому пытаются прийти к (рекурсивному) алгоритму, сводя общую задачу к "более простым" задачам того же рода. Иногда непосредственной ясно, как это сделать, но чаще всего требуется интуиция.

Пример 6. Определение операции сложения двух чисел через рекурсивные отношения.

В силу законов ассоциативности и коммуникативности имеем:

a+b=a+b+1-1=(a+1)+(b-1)

Поэтому операцию сложения можно ввести так:

function plus (a, b: integer): integer;

begin

if b=0 then plus := a

else

if b>0 then plus := plus (succ(a), pred(b))

else plus := plus (pred(a), succ(b));

end;

Если ограничиться сложением натуральных чисел, то третья ветвь отпадает.

3) вложение

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

Пример 7. Классический пример использования применения такого приема вложения дал Маккарти в 1962 г. Исходная задача звучала следующим образом: "Установи, является ли заданное положительное натуральное число n простым". При этом предполагалось, что известно определение простого числа: натуральное число называется простым, если оно больше единицы и не делится ни на одно число, большее или равное двум и меньшее этого числа.

Удачным обобщением будет такая задача (в которой вводится дополнительный параметр): "Установи, верно ли, что заданное натуральное число не делится ни на одно число, большее или равное m и меньшее этого числа".

4) метод родственных задач

При использовании этого метода к задаче "прибавляют" одну или несколько задач таким образом, чтобы функции из возникающей системы опирались друг на друга.

Пример 8. Определить, содержит ли последовательность знаков m четное число знаков. При этом справедливо утверждение: число знаков в последовательности четно тогда и только тогда, когда все знаки могут быть сгруппированы в пары.

Введем родственную задачу: Определить, содержит ли последовательность знаков m нечетное число знаков.

Обнаруживается взаимосвязь двух задач: непустая последовательность знаков содержит нечетное число знаков, только если после удаления одного знака она содержит четное число знаков, и наоборот.