Которых можно извлечь рекурсию

 

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

Пример 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).

Решение

Можно дать следующее рекурсивное определение операции сложения двух чисел:

a, еслиb=0;

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

(a-1)+(b+1), если b<0.

 

Опишем соответствующую функцию:

ProgramExample_77;

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

Найти НОД двух натуральных чисел.

Решение

Ранее мы уже рассматривали один из способов реа­лизации алгоритма Евклида. Рассмотрим еще один способ.

Имеются два натуральных числа a и b. Если a=b, то НОД(a,b)=a. Если a>b, то

НОД(a,b)=НОД(a-b,b).

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

Рассмотрим конкретный пример: найдем наиболь­ший общий делитель чисел 123 и 36 (см. таблицу).

ProgramExample_78;

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

Begin

Ifa=bThen NOD:=a

Else If a>b Then NOD:=NOD(a-b, b)

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

End;

a	b	Примечание
		Так как a>b, a:=a-b
		a:=a-b
		a:=a-b
		Так как b>a, b:=b-a
		b:=b-a
		a:=a-b
		a:=a-b
		b:=b-a
		Так как a=b, НОД:=a

 

Пример 3

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

Решение

Переведем число 23 в двоичную систему счисления. Для этого разделим его на 2, получим целую часть и остаток от деления. Целую часть снова делим на 2 и получаем целую часть и остаток. Так делаем до тех пор, пока целая часть не станет меньше делителя (то есть пока она не станет равна 1).

 

23 2

22 11 2

1 10 5 2

1 4 2 2

1 2 1

 

Теперь начиная с этой единицы выписываем в обрат­ном порядке все остатки от деления. Это и будет запись числа 23 в двоичной системе счисления:

23₁₀=10111₂

Опишем соответствующую процедуру:

ProgramExample_79;

Procedure Rec(n: Integer);

Begin

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

Write(n mod 2);

End;

Покажем вызовы процедуры для числа 23. Пер­вый вызов процедуры производится в основной про­грамме.

Результат: 10111.

Первая цифра (1) выводится на экран из послед­него вызова процедуры Reс, следующая цифра (0) - из предпоследнего и так далее, последняя (1) − из первого. Таким образом, вывод очередной цифры про­исходит перед выходом из очередного экземпляра про­цедуры Reс.

Задачи, которые можно решить как частный случай обобщенной

 

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

Пример

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

Решение

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

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

Если M=N;

Если N не делится на M и функция принимает значение "истина" для чисел М+1 и N.

ProgramExample_80;

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;

Вернемся к исходной задаче. Она является частным случаем обобщенной, если M положить равным 2. Пер­вое обращение к функции будет таким: Simple(2,N), где N − это данное число.

Задание

Изучить работу функции в пошаговом режиме и нарисовать схему вызовов функций.

Задачи, в которых можно

Использовать характеристику или свойство функции

Пример

Для заданного натурального числа N≥1 определить натуральное число a, для которого выполняется нера­венство: 2^a-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 получим a=1

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

ProgramExample_81;

Function A(n: Integer): Integer;

Begin

If N=1 Then A:=1

Else A:=A(N div 2)+1;

End;

ФАЙЛОВЫЙ ТИП ДАННЫХ