II. Задачи, из постановки которых

Можно извлечь рекурсию

В формулировках некоторых задач рекурсия не присутствует в явном виде, но их можно свети к рекурсивным.

Пример 1. Сложение двух чисел. Пусть надо сложить два целых числа a и b, а можно только прибавлять или вычитать 1. Тогда:

если b=0, то a+b=a

если b>0, то a+b=(a+1)+(b-1)

если b<0, то a+b=(a-1)+(b-1)

Это есть рекурсивное определение операций сложения двух чисел.

Function Sum(a, b: integer): integer;

Begin

if b=0 Then Sum:=a

else if b>0 Then Sum:=Sum(a+1, b-1)

else Sum:=Sum(a-1, b+1);

end;

Пример 2. Найти НОД двух натуральных чисел.(2 способ)

Имеются два натуральных числа a и b.

Если a=b, то НОД(a,b)=a.

Если a>b, то НОД(a,b)=НОД(a-b,b).

Если a<b, то НОД(a,b)=НОД(a,b-a).

Function NOD(a,b: integer): integer;

Begin

if a=b Then NOD:=a

else if a>b Then NOD:=NOD(a-b,b)

else NOD:=NOD(a,b-a);

end;

Пример 3. Перевести натуральное число из десятичной системы счисления в двоичную.

Function Rec(n: integer);

Begin

if n>1 Then Rec(n div 2);

Write(n Mod 2);

end;

III.Задачи, которые можно решить

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

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

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

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

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

· если M=N;

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

Function Simple(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.

Function A(N: integer): integer;

Begin

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

end;