Как частный случай обобщенной

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

Пример 1Определить, является ли заданное натуральное число простым.

Данную задачу можно обобщить, например, так: определить, верно ли, что заданное натуральное число N не делится ни на одно число, большее или равное М (2£M£N), но меньше N.

Соответствующая функция должна принимать значение «истина» в двух случаях:

· если M=N;

· если N не делится на М и функция принимает значение «истина» для чисел М+1 и N.

FunctionSimple(m,n : integer): boolean;

Begin

if m=n Then Simple:=True

else Simple:=(n Mod m <> 0) And Simple(m+1,n);

End;

IV. Задачи, в которых можно использовать характеристику или свойство функции

Пример 1.Для заданного натурального числа N³1 определить натуральное число a, для которого выполняется неравенство :

2^а-1 £ N < 2^a.

a(N) = 1 , если N=1

a(N)=a(N div 2) + 1, если N>1

Рассмотрим пример. Пусть N=34.

2^a-1£34<2^a, прибавим 1 и переходим к 34 div 2

2^a-1£17<2^a +1

2^a-1£ 8<2^a +1

2^a-1£ 4<2^a +1

2^a-1£ 2<2^a +1

2^a-1£ 1<2^a ; получим а=1

А теперь возвращаемся назад, к последней единице прибавляем все предыдущие. Таким образом, получается 6.

FunctionA(N : integer) : integer;

Begin

if N=1 then a:=1 else a:=a (N div 2) +1;

End;