Примеры рекурсивного программирования

Алгоритм, который в процессе работы обращает­ся сам к себе, называется рекурсивным. Для иллюст­рации понятия рекурсия часто приводят пример с те­левизором, на экране которого изображен этот же телевизор, на экране второго − опять телевизор и так далее.

Можно разбить все рекурсивные задачи на 4 вида.

Задачи с рекурсивной

Формулировкой

Некоторые объекты являются рекурсивными по оп­ределению, поэтому рекурсивные алгоритмы их получе­ния буквально повторяют соответствующие определения.

Пример

Вычисление факториала натурального числа. Для того чтобы вычислить N!, надо значение (N-1)! умножить на N, при этом 1!=1. В общем виде это можно записать так:

1 при N=1;

N!=

N(N-1)! при N>1.

Для вычисления факториала опишем функцию.

ProgramExample_76;

Function factorial (n: Integer):

Longint;

Begin

if n=1 Then factorial:=1

Else factorial:=n*factorial(n-1);

End;

Рассмотрим последовательность вызовов этой функ­ции для n=5.Первый вызов функции происходит в основной программе a:=factorial(5). Отметим, что при каждом обращении к функции будет создаваться свой набор локальных переменных (в данном случае в функции factorial имеется всего одна локальная переменная n). Для каждой локальной переменной на время работы функции выделяется память. После завер­шения работы функции эта память освобождается и пе­ременные удаляются.

Так как n≠1, то управление передается на ветку Else и функции factorial присваивается значение n*factorial(n-1), то есть 5*factorial(4). Про­исходит второй вызов функции factorial, с парамет­ром 4. Этот процесс повторяется до тех пор, пока значе­ние параметра не станет равным 1. Тогда n=1, а поэто­му значение функции factorial=1. Таким образом, n=1 − это условие окончания рекурсии. Управление пе­редается в точку вызова, то есть в предыдущую функцию для n=2 factorial:=n*factorial(n-1), значит, factorial: =2*1, следовательно, factorial(2)=2. Возвращаемся назад, поднимаясь "вверх" по цепочке ре­курсивных вызовов. Таким образом, получаем значение factorial(5)=120, это значение и присваивается пе­ременной а.

Задачи, из постановки

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

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

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

Пример 3

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

Решение

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

23 2   

22 11 2

              1 10 5 2

              1 4 2 2

                     1 2 1          

                                 0

Теперь начиная с этой единицы выписываем в обрат­ном порядке все остатки от деления. Это и будет запись числа 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с.