Материалы к урокам по теме "Рекурсивные алгоритмы"

1. Общие вопросы

Алгоритм называется “рекурсивным” ¹, если он вызывает сам себя в качестве вспомогательного. Часто в основе рекурсивного алгоритма лежит так называемое “рекурсивное определение” какого-то понятия. Оно имеет место, когда понятие сводится к аналогичному, но более простому понятию. Пример — “Задача о коровах”.

“Задача о коровах”

Есть два утверждения:

1) три коровы — это стадо коров;

2) стадо из n > 3 коров — это стадо из n – 1 коровы и еще одна корова,

— о которых можно сказать, что это — рекурсивное определение понятия “стадо коров”.

Необходимо, используя это определение, проверить, является ли стадом группа из пяти коров (обозначим ее К5).

Решение

Объект К5 не удовлетворяет первому пункту определения, поскольку пять коров — это не три коровы. Согласно второму пункту, К5 — стадо, если там есть одна корова, а остальная часть К5, назовем ее К4, тоже является стадом коров. Итак, решение относительно объекта К5 откладывается, пока не будет принято решение в части К4.

Объект К4 также не соответствует первому пункту, а согласно второму пункту К4 является стадом, если объект К3, полученный из К4 путем отделения одной коровы, тоже стадо. Решение о К4 тоже откладывается.

Наконец, объект К3 удовлетворяет первому пункту определения, и мы можем смело утверждать, что К3 — стадо коров. Теперь и о К4 можно утверждать, что это стадо, а значит, и К5 является стадом коров.

Примечание. Решение целесообразно сопровождать изображением схемы (см. рис. 1).

Вот еще одно рекурсивное определение: о факториале числа N можно сказать, что N! = N * (N – 1)!, если N > 0 и N! = 1, если N = 0.

Любое рекурсивное определение состоит из двух частей. Эти части принято называть “базовой” и “рекурсивной”. Базовая часть является нерекурсивной и задает определение для некоторой фиксированной части объектов. Рекурсивная часть определяет понятие через него же и записывается так, чтобы при цепочке повторных применений она сводилась бы к базовой части ².

Так и, разрабатывая программу, часто удается свести исходную задачу к более простым задачам. Среди них может оказаться и первоначальная задача, но в упрощенной форме. Например, вычисление функции F(n) может потребовать вычисления F(n – 1) и еще каких-то операций. Иными словами, частью алгоритма вычисления функции будет вычисление этой же функции.

Аналогично рекурсивному алгоритму, “рекурсивной” называется функция (или процедура), если она обращается к самой себе как вспомогательной.

Пример. Рекурсивная функция для расчета факториала заданного числа n:

Function F(n: byte): longint;
Begin
If n > 1 Then F := n * F(n – 1)
Else F := 1
End;

2. Особенности выполнения рекурсивных алгоритмов

Учитель: “Рассмотрим программу, в результате выполнения которой на экран выводится текст истории о попе и его собаке (“У попа была собака…”)”.

На доске записывается текст программы:

Program History;
Procedure Print;
Begin
   Writeln ('У попа была собака,');
   Writeln ('Он ее любил.');
   Writeln ('Она съела кусок мяса —');
   Writeln ('Он ее убил.');
   Writeln ('Убил и закопал');
   Writeln ('И на могиле написал:');
   Print; {Рекурсивный вызов процедуры Print}
   Readkey {Ожидание нажатия любой клавиши}
End;
BEGIN {Основной программы}
   Print
END.

Учитель: “Сколько раз текст истории будет выведен на экран?”.

В ходе обсуждения необходимо рассказать (напомнить), что при каждом вызове вспомогательной процедуры (функции) для нее отводится место в оперативной памяти, которое “освобождается” после завершения ее (процедуры) работы. Но если во вспомогательной процедуре имеется рекурсия, то вызовы вспомогательных процедур будут продолжаться до тех пор, когда выделенное место в памяти будет исчерпано (в результате на экране появится сообщение об ошибке, связанной с этим фактом) ³.

Чтобы устранить этот недостаток, необходимо так оформлять процедуры (функции), чтобы рекурсивные вызовы осуществлялись по условию, которое когда-то станет ложным.

Например, в рассмотренной программе должна быть описана процедура с параметром и использован условный оператор:

Program History;
Procedure Print (Var n: byte);
Begin
If n > 0 Then
Begin
n := n - 1;
Writeln ('У попа была собака,');
End
End;
BEGIN {Основной программы}
Print(20)
END.

Для объектов с рекурсивным определением при ложном значении условия должна выполняться базовая часть определения (см. функцию F для нахождения факториала заданного числа n в разделе 1).

Последовательность рекурсивных вызовов функции F при n = 3 показана на рис. 2.

Выполнение оператора x := F(3) в основной части программы требует первого обращения к функции F.
В оперативной памяти выделено место для размещения этой функции, а параметру n будет присвоено значе-
ние 3. Начнется выполнение функции. Так как n > 1, то будет выполнена ветвь условного оператора, содержащая рекурсию:

F := 3 * F(2)

В результате будет опять вызвана функция F и ей будет передано значение n = 2. При выполнении функции также “сработает” рекурсивная ветвь:

F := 2 * F(1)

что потребует очередного размещения в памяти функции F с параметром n = 1. При ее выполнении рекурсивного вызова не будет (согласно базовой части F = 1). Найденное значение F(1) = 1 будет передано в функцию, откуда была вызвана функция F с параметром n = 1, после чего место, выделенное под последнюю функцию, освободится ⁴. В результате будет рассчитано значение F(2) = 2, которое также “вернется” в вызывающую функцию для определения значения F(3). Это значение F(3), равное 6, будет возвращено в основную часть программы и присвоено переменной х.

От редакции. Механизм организации работы рекурсивных процедур (функций) подробно описан в статье Е.А. Еремина “Стек”, опубликованной в “Информатике” № 2–4/2008.

3. Рекурсивные функции и процедуры для обсуждения

Три первые функции представляются учащимся на доске или в виде раздаточного материала. Необходимо определить, что выполняет каждая из них.

Остальные процедуры и функция Аккермана разрабатываются в процессе обсуждения (для их записи к доске вызывается один из учеников).

После обсуждения целесообразно предложить учащимся решить рассмотренные задачи на компьютере.

1.

Function K(a: longint): byte;
Begin
   If a < 10 Then k := 1
   Else K := 1 + K(a Div 10)
End;

Ответ. Функция вычисляет количество цифр в заданном натуральном числе a.

Комментарии

Если число — параметр функции меньше 10, то количество цифр в нем равно 1, иначе значение функции равно сумме единицы и числа, полученного путем “отбрасывания” последней цифры числа-параметра. Указанное число будет при каждом вызове функции уменьшаться в 10 раз до тех пор, пока не “сработает” базовая часть рекурсивного описания функции K.

2.

Function F(k: byte): longint;
Begin
If (k = 1) Or (k = 2) Then F := 1
Else
F := F(k — 1) + F(k — 2)
End;

Ответ. Функция вычисляет k-й член последовательности Фибоначчи, первые два члена которой равны 1, каждый последующий есть сумма двух предыдущих (1, 1, 3, 5, 8, …).

3.

Function S(k: byte): longint;
Begin
If k = 1 Then S := a[k]
Else S := a[k] + S(k — 1)
End;

Ответ. Функция определяет сумму элементов заданного числового массива a, элементами которого являются целые числа.

Комментарии

Параметр функции: k — количество элементов массива, сумма которых рассчитывается при каждом вызове функции. Когда k = 1, то значение функции равно единственному элементу такого массива, иначе — сумме последнего элемента и значения этой же функции для массива без учета последнего элемента.

От редакции. В приведенном виде функция может быть использована для решения задачи только применительно к массиву с именем a. Для создания функции, которая может “обрабатывать” любые массивы одного типа, следует обрабатываемый массив сделать параметром функции.

4. Процедура вывода цифр p-ичного представления заданного десятичного натурального числа (2≤p≤9).

Разбор задачи

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

Обозначим заданное десятичное число — n. Для его перевода в p-ичную систему счисления требуется определение остатка от деления на p числа n и затем промежуточных частных до тех пор, пока не получится частное, меньшее p. Но если процедуру, обеспечивающую определение и вывод остатков (имя величины — remin), оформить в виде:

Procedure From10(a: longint; p: byte);
Var remin: byte;
Begin
{Определяем остаток}
remin := a mod p;
{Выводим его}
write(remin);
{Если нужно, делаем то же самое для промежуточного частного}
If a >= p Then From10(a div p, p)
End;

— то цифры будут выведены, начиная с последней. Для получения требуемого результата необходимо определение и вывод остатков проводить после рекурсивного вызова процедуры:

Procedure From10(a: longint; p: byte);
Var remin: byte;
Begin
{Если нужно, вызываем процедуру From10 для промежуточного частного}
If a >= p Then From10(a div p, p);
{Определяем остаток для текущих значений параметров процедуры}
remin := a mod p;
{Выводим его}
write(remin)
End;

От редакции. Последний вариант рекурсивной процедуры называется “Форма с выполнением действий после рекурсивного вызова (или с выполнением действий на рекурсивном возврате)”. Возможны также форма с выполнением действий до рекурсивного вызова (или с выполнением действий на рекурсивном спуске) и форма с выполнением действий как до, так и после рекурсивного вызова (или с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате) — см. Златопольский Д.М. Программирование: типовые задачи, алгоритмы, методы. М.: БИНОМ. Лаборатория знаний, 2007. Схемы этих трех вариантов и примеры их применения приведены в разделе ⁵.

5. Вывод всех делителей натурального числа.

Разбор задачи

Сначала рассматривается и обсуждается программа:

Var n, d: longint;
BEGIN
...
For d := 1 To n div 2 Do
If n div 2 = 0 Then write(n div d, ' ')
write(n)
...

В ней находятся и выводятся все делители числа n. Например, для n = 30 будут выведены числа 1, 2, 3, 5, 6, 10, 15, 30.

Далее надо заметить, что для того чтобы найти делители числа n, достаточно обнаружить делители, не превышающие , — все остальные делители получаются в результате деления n на найденные делители.

Фрагмент программы, учитывающий это обстоятельство:

For d := 1 To Trunc(Sqrt(n)) — 1 Do
If n mod d = 0 Then write(d, ' ', n div d, ' ');
If Sqr(Trunc(Sqrt(n))) = n then write(Trunc(Sqrt(n)));

Последний оператор используется для того, чтобы в случае, когда n — точный квадрат, делитель, равный , не выводился дважды. В результате, когда n = 100, будут выведены числа:

1, 100, 2, 50, 4, 25, 5, 20, 10.

А как сделать так, чтобы делители были напечатаны в порядке возрастания?

Ответ — надо использовать рекурсию. Процедура, решающая рассматриваемую задачу, имеет вид:

Procedure Dived(n, d: longint);
Var dd: longint;
{dd — делитель, 'симметричный' найденному делителю}
Begin
If n mod d = 0 Then
{Встретился делитель числа n}
Begin
{Выводим его}
write(d, ' ');
{Запоминаем 'симметричный' делитель}
dd := n div d;
If d <> dd Then
Begin
{Переходим к проверке следующего числа d}
Dived(n, d + 1);
{После 'возврата' из процедуры Dived печатаем делитель dd}
write(dd, ' ')
End
End
Else {n mod d <> 0}
{Переходим к проверке следующего числа d}
Dived(n, d + 1)
End;

Вызов процедуры из основной программы осуществляется следующим образом:

Dived(n, 1);

От редакции. Здесь используется форма рекурсивной процедуры с выполнением действий как до, так и после рекурсивного вызова (или с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате).

6. Процедура получения и вывода на экран всех вариантов разложения заданного натурального числа n на множители (без повторений).

Разбор задачи

Решение будем получать в строковом виде, аналогичном следующему (для n = 12):

2*2*3

2*6

…

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

Параметрами создаваемой рекурсивной процедуры (ее имя — R) будут:

k — число, разлагаемое на множители (не только заданное);

first — первый возможный множитель числа k;

s — величина строкового типа, представляющая собой запись разложения, полученного до вызова процедуры R.

Искать возможные множители можно не до целой части от k/2, а до целой части квадратного корня из k (см. обсуждение предыдущей задачи).

Что делается в процедуре R?

Необходимо проверить, являются ли множителями числа k числа m, равные first, first + 1,( —   целая часть квадратного корня из k). Если множитель (очередной) встретился, то необходимо:

1) его строковое представление sm “добавить” к уже полученной ранее записи s с учетом символа “*” — полученная величина (s2) будет передана в качестве параметра при очередном рекурсивном вызове процедуры R;

2) вызвать процедуру R с параметрами k div m, m, s2.

После проверки всех чисел m необходимо учесть в записи разложения также число k и вывести полученный результат на экран.

Процедура R, решающая задачу:

Procedure R(k, first: longint; s: string);
Var m: word;
sm, s2: string; {sm — строковое представление очередного множителя}
Begin
For m := first to Trunc(Sqrt(k)) Do
{Если m — множитель числа k}
If k mod m = 0 Then
Begin {то: — получаем строковое представление m,}
Str(m, sm);
{— добавляем его к ранее полученной записи разложения}
s2 := s + sm + '*'
{— вызываем (рекурсивно) процедуру R с новыми параметрами}
R(k div m, m, s2)
End;
{После рассмотрения всех возможных множителей учитываем в разложении также число k}
Str(k, s2);
s := s + s2;
writeln(s)
End;

Вызов разработанной процедуры из основной части программы должен выглядеть следующим образом: R(n, 2, '');

После обсуждения программы целесообразно предложить учащимся проследить последовательность рекурсивных вызовов процедуры R.

От редакции. В приведенном виде процедуры последнее разложение будет представлять собой строковое представление числа n (без множителя, равного 1), например, для случая n = 12: 12. Для получения вида, аналогичного следующему: 1*12, необходимо:

1) последний фрагмент процедуры оформить в виде:

If k <> n Then
Begin
Str(k, s2);
s := s + s2;
writeln(s)
End

2) в основной части программы первое (известное!) разложение получить так: writeln(1, '*', n);

7. Функция Аккермана

Учитель сообщает, что функция Аккермана для неотрицательных чисел m и n определяется следующим образом:

Соответствующая рекурсивная функция

Function Akk(n, m: byte): word;
Begin
If n = 0 Then Akk := m + 1
Else
If (n <> 0) And (m = 0)
Then Akk := Akk(n — 1, 1)
Else
If (n > 0) And (m >= 0) Then
Akk := Akk(n — 1, Akk(n, m — 1))
End;

От редакции

1. Функцию Аккермана называют “дважды рекурсивной”, т.к. сама функция и один из ее аргументов определены через самих себя.

2. Расчет значения функции Аккермана даже при небольших значениях параметров n и m требует значительных объемов памяти для размещения функции при рекурсивных вызовах (см. раздел 2). Можно предложить учащимся проверить это утверждение, например, при n = 4, m = 5.

4. Задания на использование рекурсии

Приведенные задания могут быть использованы на “обычных” уроках, на контрольных мероприятиях, как задания на дом и т.п. 5

1. Разработать программу для расчета числа сочетаний из n элементов по m (обозначается ), используя следующее рекурсивное описание:

Решение

Рекурсивная функция для расчета значения  :

Function Cnm(n, m: byte): word;
Begin
If (m = 0) Or (n = m) Then Cnm := 1
Else Cnm := Cnm(n — 1, m) + Cnm(n — 1, m — 1)
End;

2. Составить программу для расчета n-го члена заданной арифметической прогрессии.

Решение

Можно сказать, что в определении понятия “арифметическая прогрессия” содержится рекурсивное описание искомого значения.

В приведенной ниже функции, кроме n, используются также параметры а1 и d — соответственно первый член прогрессии и ее разность:

Function Ar_n(a1, d: real; n:byte): real;
Begin
If n = 1 Then Ar_n := a1
Else Ar_n := Ar_n(a1, d, n — 1) + d
End;

3. Составить программу для расчета n-го члена заданной геометрической прогрессии.

Решение

Здесь рекурсивная функция во многом аналогична приведенной в предыдущей задаче:

Function Geo_n(a1, z: real; n: byte): real;
Begin
If n = 1 Then Geo_n := a1
Else Geo_n := Geo_n(a1, z, n — 1) * z
End;

— в ней z — знаменатель прогрессии.

4. Составить программу для расчета суммы n первых членов заданной арифметической прогрессии.

Решение

В приведенной ниже функции в качестве вспомогательной используется функция, описанная в задаче 2:

Function Summ_Ar_n(a1, d: real; n: byte): real;
Begin
If n = 1 Then Summ_Ar_n := a1
Else Summ_Ar_n := Summ_Ar_n(a1, d, n — 1) + Ar_n(a1, d, n)
End;

5. Составить программу для расчета суммы n первых членов заданной геометрической прогрессии.

Решение

Соответствующая функция:

Function Summ_Geo_n(a1, d: real; n: byte): real;
Begin
If n = 1 Then Summ_Geo_n := a1
Else Summ_Geo_n := Summ_Geo_n(a1, d, n — 1) + Geo_n(a1, d, n)
End;

6. Дана строка символов, представляющая собой правильную запись натурального числа в p-ичной системе счисления (2≤p≤9). Составить программу перевода этого числа в десятичную систему счисления.

Решение

Здесь надо вспомнить схему Горнера для расчета десятичного значения числа по его цифрам, которая по сути является рекурсивной. Так, если число в p-ичной системе является четырехзначным (а₃а₂а₁а₀), то десятичное значение этого числа определяется следующим образом:

((а₃· p + а₂) · p + а₁) · p + а₀.

Функция, “работающая” по этой схеме, может иметь вид:

Function RevTo10(S: string; p: byte): longint;
Var last: byte; code: integer; {last — последняя цифра в строковой записи числа)
Begin
If length(S) = 1 Then
Begin
{Переводим символ-цифру в число,}
Val(S[Length(S)], last, code);
{которое и будет значением функции}
RevTo10 := last
End
Else
Begin
{Переводим последний символ строки S в число last}
Val(S[Length(S)], last, code);
{и используем схему Горнера}
RevTo10 := RevTo10(Copy(S, 1, Length(S) — 1), p) * p + last
End
End;

Можно также сначала перевести в число всю строку S, а затем “работать” с его цифрами:

Function RevTo10(S: string; p: byte): longint;
Var k: longint; last: byte;
code: integer;
{k — число, соответствующее S)
Begin
{Определяем число k)
Val(S, k, code);
If k < 10 Then RevTo10 := k
Else
Begin
{Определяем последнюю цифру числа k)
last := k mod 10;
{Переводим число k без его последней цифры в символьное представление}
Str(k div 10, s);
{и используем схему Горнера}
RevTo10 := R_to10(s, p) * p + last
End
End;

7. Разработать программу для определения суммы цифр заданного натурального числа.

Решение

Соответствующая рекурсивная функция во многом аналогична функции, рассмотренной в разделе 3.

Function S(a: longint): byte;
Begin
If a < 10 Then S := a
Else S := a mod 10 + S(a div 10)
End;

8. Разработать программу для вычисления произведения элементов одномерного числового массива.

Решение

Функция, с помощью которой можно решить задачу, также аналогична рассмотренной в разделе 3.

Function M(k: byte): real;
Begin
If k = 1 Then M := a[k — 1]
Else M := a[k] * M(k — 1)
End;

Примечание. Имеется в виду, что элементы массива а — вещественные числа.

От редакции. Здесь и в других задачах, связанных с использованием массивов, можно учесть замечание, сделанное при обсуждении функции для расчета суммы элементов массива в разделе 3.

9. Разработать программу для расчета среднего арифметического всех элементов числового массива.

Решение

Рекурсивная функция, которая возвращает искомое значение, имеет вид:

Function Aver(k: byte): real;
{k — число элементов обрабатываемого массива}
Begin
If k = 2 Then Aver := (a[1] + a[k])/2
Else Aver := (a[k] + Aver(k — 1) * (k — 1))/k
End;

10. Разработать программу для расчета значения an (a — вещественное число, a № 0, n — целое).

Решение

Можно записать:

Рекурсивная функция:

Function Power(a: real; n: integer): real;
Begin
If n = 0 Then Power := 1
Else
If n > 0 Then Power := a * Power(a, n — 1)
Else Power := 1/(Power(a, Abs(n)))
End;

Примечание. Целесообразно обсудить с учащимися последовательность вызовов и использования приведенной функции при отрицательных значениях n, например, n = –3.

11. Разработать программу для нахождения наибольшего общего делителя (НОД) двух заданных натуральных чисел.

Решение

Можно применить алгоритм Евклида нахождения НОД. Его суть в следующем: “Если два заданных числа равны, то в качестве ответа взять любое, иначе большее из чисел заменить разностью большего и меньшего”.

В аналитическом виде алгоритм Евклида выглядит следующим образом:

Рекурсивная функция, реализующая этот алгоритм:

Function NOD(a, b: word): word;
Begin
If a = b Then NOD := a
Else
If a > b Then NOD := NOD(a — b, b)
Else NOD := NOD (a, b — a)
End;

12. Разработать программу для определения значения минимального элемента массива.

Решение

Опишем функцию MinK, которая определяет минимум в массиве а из k элементов. Ясно, что если k = 2, то результат равен минимальному из первых двух элементов массива. Если же k > 2, то результатом является минимальное из двух чисел: последнего элемента такого массива и минимального числа из первых (k – 1) элементов массива. Второе из сравниваемых чисел можно найти с помощью той же функции MinK (рекурсивный вызов).

Соответствующая рекурсивная функция

Function MinK(k: byte) : integer;
Begin
If k = 2 Then MinK := Min(a[1], a[k])
Else MinK := Min(a[k], MinK(k — 1))
End;

Минимальное из двух чисел определяется с помощью функции Min, параметрами которой являются эти числа:

Function Min(a, b: integer): integer;
Begin
If a > b Then Min := b
Else Min := a
End;

Чтобы найти минимум среди всех элементов заданного массива, нужно вызвать функцию MinK, указав в качестве фактического параметра размер массива.

От редакции. Можно в заголовке функции использовать только один параметр — k, а в ее теле значение last заменить на a[k]:

Function MinK(k: byte): integer;
Begin
If k = 2 Then MinK := Min(a[1], a[2])
Else MinK := Min(a[k], MinK(k — 1))
End;

13. Разработать программу для определения индекса минимального элемента массива.

Решение

Если в массиве два элемента (k = 2), то результатом является индекс одного из двух первых элементов. Если же n > 2, то результат определяется путем сравнения двух элементов: k-го и того, который является минимальным среди первых (k – 1) элементов массива. Индекс второго из сравниваемых чисел можно найти, используя рекурсию.

Соответствующая рекурсивная функция:

Function IndMinK(k: byte): byte;
Begin
If k = 2 Then IndMinK := IndMin2(1, k)
Else IndMinK := IndMin2(k, IndMinK(k — 1))
End;

— где IndMin2 — функция определения индекса минимального из двух элементов массива с заданными индексами:

Function IndMin2(ind1, ind2: byte): byte;
{ind1, ind2 — индексы сравниваемых элементов}
Begin
If a[ind1]< a[ind2] Then IndMin2 := ind1
Else IndMin2 := ind2
End;

Примечание. Целесообразно предложить учащимся подумать над вопросом: “Индекс какого элемента будет найден, если в массиве есть несколько элементов с минимальным значением?”.

14. Используя оператор write(а) лишь при а = 0..9, разработать программу вывода на экран десятичной записи заданного натурального числа n.

Решение

Процедура, обеспечивающая решение задачи:

Procedure Print(n: longint);
Begin
If n < 10 Then
Begin
a := n;
write(a)
End
Else
Begin
{Рекурсивный вызов процедуры Print}
Print(n div 10);
{Определение и вывод последней цифры числа n}
a := n mod 10;
write(a)
End
End;

Здесь также имеет место так называемая “Форма рекурсивной процедуры с выполнением действий после рекурсивного вызова (или с выполнением действий на рекурсивном возврате)” — см. раздел 5. — Прим. ред.

15. Разработать программу, которая вычисляет длину заданной строки (стандартную функцию Length не использовать).

Решение

В рекурсивной функции применяется стандартная процедура Delete:

Function Len(s: string): byte;
Begin
If S = '' Then Len := 0
Else
Begin
Delete(s, 1, 1);
Len := 1 + Len(s)
End
End;

16. Разработать программу, проверяющую, является ли некоторая строка палиндромом (т.е. читается одинаково слева направо и справа налево).

Решение

Рекурсивная функция, возвращающая результат логического типа, с помощью которой можно решить задачу, имеет вид:

Function Pal(s: string): boolean;
Begin
{Если строка 'пустая' или состоит из одного символа}
If (s = '') Or (Length(s) = 1)
Then Pal := true
Else
{Сравниваем первый и последний символы строки}
If s[1] <> s[Length(s)] Then Pal := false
Else
{Удаляем первый и последний символы строки}
Begin
Delete(s, 1, 1);
Delete(s, Length(s), 1);
{и вновь проверяем оставшуюся строку}
Pal := Pal(s)
End
End;

Эта функция используется в основной части программы при выводе ответа:

If Pal(st)

Then writeln('Строка является палиндромом'}

Else writeln('Строка не является палиндромом'};

— где st — проверяемая строка.

Можно также процедуру Delete не применять, а при рекурсивном вызове использовать функцию Copy.

17. Разработать программу расчета суммы двух натуральных чисел, используя только прибавление единицы.

Решение

Рекурсивная функция Summa1, возвращающая число а как результат сложения а единиц, может быть оформлена в виде:

Function Summa1(a: byte): word;
Begin
If a = 1 Then Summa1 := 1
Else Summa1 := 1 + Summa1(a — 1)
End;

Эта функция используется в основной части программы для подсчета искомого результата rez:

rez := Summa1(n1) + Summa1(n2);

— где n1 и n2 — складываемые числа.

18. Разработать программу расчета произведения двух натуральных чисел, используя только операцию сложения.

Решение

Рекурсивная функция, возвращающая произведение двух своих параметров a1 и a2 как результат многократного сложения, имеет вид:

Function Mult(a1, a2 : byte): longint;
Begin
If a2 = 1 Then Mult := a1
Else Mult := a1 + Mult(a1, a2 — 1)
End;

Возможен также “симметричный” вариант, в котором происходит a1 сложений числа a2, а также “общий” вариант, в котором после сравнения a1 и a2 выбирается оптимальный с точки зрения количества операций сложения.

19. Разработать программу для вывода заданной последовательности чисел,           оканчивающейся нулем, в обратном порядке.

Решение

В соответствующей рекурсивной процедуре используется локальная переменная n — очередное число последовательности:

Procedure Output;
Var n: integer;
Begin
write('Введите очередное число последовательности');
readln(n);
If n <> 0 Then
Begin
{Рекурсивно вызываем процедуру Output для ввода очередного числа}
Output;
{После 'возвращения' из нее выводим введенное число}
write(n, ' ')
End
Else
write('Числа последовательности в обратном порядке:')
End;

20. Задача “Ханойские башни”.

Имеется три стержня А, В, С. На стержень А нанизаны n дисков таким образом, что диаметр дисков увеличивается при их просмотре сверху вниз. Требуется переместить все диски на стержень В, используя диск С как вспомогательный и соблюдая следующие правила:

1) перекладывать диски можно по одному;

2) снятый диск нельзя отложить — он должен быть надет на один из стержней;

3) диски нельзя размещать на дисках меньшего размера.

Решение

Если диск один — задача решается одним перемещением. Сложнее, если дисков больше. Предположим, что мы умеем перекладывать пирамиду из (n – 1) диска. Тогда для перемещения n дисков необходимо:

1) переместить верхние (n – 1) дисков на стержень С;

2) перенести последний, самый большой, диск со стержня А на стержень В;

3) переместить пирамиду из (n – 1) дисков со стержня С на стержень В.

Решение задачи для (n – 1) дисков аналогично. В результате таких рекурсивных действий можно прийти к ситуации, когда количество перемещаемых дисков равно 1, а такую задачу мы решать умеем.

В программе следует использовать две процедуры, одна из которых — рекурсивная:

1) процедуру перемещения одного диска:

Procedure MoveOneDisk(a, b: char);
Begin
Write(a, '->', b, ' ')
End;

2) процедуру перемещения n дисков:

Procedure MoveDisks(n: byte; a, b, c: char);
Begin
If n = 1 Then
{Используем процедуру MoveOneDisk}
MoveOneDisk(a, b)
Else
Begin
MoveDisks(n — 1, a, c, b);
write(a,'->', b, ' ');
MoveDisks(n — 1, c, b, a)
End
End;

Можно также задачу при n = 1 отдельно не рассматривать:

Procedure MoveDisks(n: byte; a, b, c: char);
Begin
If n > 0 Then
Begin
MoveDisks(n — 1, a, c, b);
write(a,'->', b, ' ');
MoveDisks(n — 1, c, b, a)
End
End;

5. Прямая и косвенная рекурсия

“Обычная” рекурсия, при которой процедура или функция обращается к самой себе, называется “прямой рекурсией”. Существует также разновидность рекурсии, которую называют косвенной, или непрямой. Такой рекурсией является ситуация, когда процедура А вызывает себя в качестве вспомогательной не непосредственно, а через другую вспомогательную процедуру Б, которая, в свою очередь, обращается к процедуре А.

Косвенную рекурсию демонстрирует следующая программа, в которой находятся и выводятся все простые числа, не превышающие некоторого значения n.

Создадим функцию логического типа с именем Prim, проверяющую, является ли число i — ее параметр, простым. Чтобы ответить на этот вопрос, достаточно проверить делимость i на все простые числа, не превышающие квадратный корень из i. Перебор таких простых чисел можно организовать так: рассмотреть первое простое число — 2, а затем использовать функцию NextPrim, возвращающую следующее за значением ее параметра простое число:

Function Prim(j: word): boolean;
Var k: word;
Begin
k := 2; {первое простое число}
While (k * k <= j) And (j mod k <> 0) Do k := NextPrim(k);
{Значение k 'пробегает' последовательность простых чисел, начиная с 2 и до корня из j, при этом проверяется, делится ли j на одно из таких простых чисел}
If j mod k = 0
{Если встретилось составное число}
Then Prim := false Else Prim := true
End;

Функцию же NextPrim можно оформить так:

Function NextPrim(i: word): word;
Var p: word;
Begin
p := i + 1;
While not(Prim(p)) Do p := p + 1;
NextPrim := p
End

В ней проверяются на “простоту” числа p, начиная со значения, на 1 большего значения параметра i, и делается это с помощью функции Prim (т.е. функция Prim вызывает функцию NextPrim, а последняя обращается к Prim, т.е. имеет место косвенная рекурсия).

При косвенной рекурсии возникает проблема — если первой описать функцию Prim, то она будет использовать еще не описанную функцию NextPrim, что в языке программирования Паскаль недопустимо (аналогично и если, наоборот, первой описать функцию NextPrim). Выходом является так называемое “опережающее описание” функции. Оно заключается в том, что заголовок одной из функций указывается первым со служебным словом Forward:

Function NextPrim(i: word): word; Forward;

— после чего полностью описывается вторая функция:

Function Prim(j: word): boolean;
Var k: word;
Begin
…

а затем — первая функция:

Function NextPrim;
Var p: word;
Begin
…

Обращаем внимание на то, что в полном описании функции NextPrim в заголовке список формальных параметров и тип результата не указываются (они уже объявлены ранее).

Заметим также, что число 2 — простое, а число 1 простым не считается. Это означает, что значение 2 в основной программе должно быть выведено без проверки, которая проводится с помощью функции Prim для всех нечетных чисел, не превышающих n.

5. Формы рекурсивных процедур ⁶

В общем случае любая рекурсивная процедура Р включает в себя некоторое множество операторов Д и один или несколько операторов рекурсивного вызова Р. Структура рекурсивных процедур может принимать три разных формы.

1. Форма с выполнением действий после рекурсивного вызова (или с выполнением действий на рекурсивном возврате). Ее схема:

алг Р
нач
если <условие>
то
Р
все
Д
кон

или

алг Р
нач
если <условие>
то
Р
Д
все
кон

Примеры такой процедуры:

алг ВыводЧисла(арг цел n)
нач
если n > 1
то
ВыводЧисла(n — 1) все
вывод n, " "
кон

или

алг ВыводЧисла(арг цел n)
нач
если n > 0
то
ВыводЧисла(n — 1)
вывод n, " "
все
кон

Нетрудно предсказать результат их выполнения, например, при n = 5: 1 2 3 4 5.

2. Форма с выполнением действий до рекурсивного вызова (или с выполнением действий на рекурсивном спуске). Ее схема:

алг Р
нач
Д
если <условие>
то
Р
все
кон

или

алг Р
нач
если <условие>
то
Д
Р
все
кон

Примеры:

алг ВыводЧисла(арг цел n)
нач
вывод n, " "
если n > 1
то
ВыводЧисла(n — 1)
все
кон

или

алг ВыводЧисла(арг цел n)
нач
если n > 0
то
вывод n," "
ВыводЧисла(n — 1)
все
кон

Результат (при n = 5): 5 4 3 2 1.

3. Форма с выполнением действий как до, так и после рекурсивного вызова (или с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате). Ее схема:

алг Р
нач
Д
если <условие>
то
Р
все
Д
кон

или

алг Р
нач
если <условие>
то
Д
Р
Д
все
кон

Примеры:

алг ВыводЧисла(арг цел n)
нач
вывод n, " "
если n > 1
то
ВыводЧисла(n — 1)
все
вывод n, " "
кон

или

алг ВыводЧисла(арг цел n)
нач
если n > 0
то
вывод n, " "
ВыводЧисла(n — 1)
вывод n, " "
все
кон

Их результат: 5 4 3 2 1 1 2 3 4 5.

Задания для самостоятельной работы учащихся

Предсказать результат выполнения следующих процедур при a = 4:

1)

алг П1(арг цел a)
нач
если a > 1
то
П1(a — 1)
все
вывод a * а, " "
кон

Ответ: 1 4 9 16.

2)

алг П2(арг цел a)
нач
если a > 0
то
П2(a — 1)
вывод –a, " "
все
кон

Ответ: при n = 5: –1 –2 –3 –4.

3)

алг П3(арг цел a)
нач
вывод 2 * a, " "
если a > 1
то
П3(a — 1)
все
кон

Ответ: 8 6 4 2.

4)

алг П4(арг цел a)
нач
если a > 0
то
вывод a * а * а, " "
П4(a — 1)
все
кон

Ответ: 64 27 8 1.

5)

алг П5(арг цел a)
нач
вывод a * a
если a > 1
то
П5(a — 1)
все
вывод a * а, " "
кон

Ответ: 16 9 4 1 1 4 9 16.

6)

алг П6(арг цел a)
нач
если a > 0
то
вывод a, " "
П6(a — 1)
вывод a, " "
все
кон

Ответ: 8 6 4 2 2 4 6 8.

6. Теоретические вопросы по теме

1. Что такое рекурсия?

2. Какое определение понятия называется “рекурсивным”? Приведите примеры.

3. Что такое базовая и рекурсивная часть рекурсивного определения понятия? Укажите эти части в приведенных ранее примерах.

4. Какое значение имеет базовая часть рекурсивного описания?

5. Какая функция (процедура) называется “рекурсивной”?

6. Как должна быть оформлена рекурсивная функция (процедура), чтобы ее вызовы не продолжались “бесконечно”?

7. Что происходит в оперативной памяти при рекурсивном вызове функции (процедуры)?

8. Что такое “косвенная рекурсия”?

9. Какая проблема возникает в программе на языке Паскаль при использовании косвенной рекурсии? Как она решается?

10. Какие возможны формы рекурсивных процедур? В чем особенность каждой из них? Приведите примеры.

Рекурсивные алгоритмы — послесловие

Знакомство учащихся с понятием “рекурсия” и примерами использования ее в программировании является, безусловно, полезным, особенно при изучении информатики на профильном уровне. Рекурсия является удобным средством решения большого числа задач. Одна из них — задача нахождения k-го члена последовательности Фибоначчи (см. раздел 3 в статье Н.А. Медведьковой). Вот как пришлось бы оформить соответствующую функцию (для универсальности приведем вариант на школьном алгоритмическом языке):

алг цел Фиб(арг цел k)
нач цел очер, пред, предпред, i
пред := 1
предпред := 1
нц для i от 2 до k — 2
очер := пред + предпред
предпред := пред
пред := очер
кц
знач := очер |Значение функции
кон

В ней использованы следующие величины:

очер — очередной рассчитываемый элемент последовательности;

пред — элемент, предшествующий очередному элементу;

предпред — элемент, предшествующий элементу пред.

А теперь посмотрите, как просто и логично выглядит рекурсивный вариант функции:

алг цел Фиб(арг цел k)
нач
если k > 2
то
{Рекурсивный вызов функции Фиб}
знач := Фиб(k — 2) + Фиб(k — 1)
иначе
знач := 1
все
кон

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

Другие показательные примеры — задачи, связанные с прогрессиями (см. задачи 2–5 в статье Н.А. Медведьковой). При их решении с применением рекурсии можно не вспоминать нужные формулы (J).

Одним из самым ярких примеров использования рекурсии является метод сортировки числовых массивов, разработанный в 1962 г. в Англии профессором Оксфордского университета Ч.Хоаром (С.Hoare). Этот метод, считающийся самым быстрым из всех известных, основан на рекурсии (см., например, книгу Д.М. Златопольского “Программирование: типовые задачи, алгоритмы, методы”. М.: БИНОМ. Лаборатория знаний, 2007).

В то же время следует обратить внимание на то, что применение рекурсивных процедур и функций в ряде случаев нерационально. Здесь, как ни странно, необходимо вспомнить все ту же задачу определения k-го члена последовательности Фибоначчи. Приведенная выше рекурсивная функция работает весьма неэффективно. Фиб(17) вычисляется в ней как Фиб(16) + Фиб(15). Фиб(16), в свою очередь, определяется как Фиб(15) + Фиб(14). Таким образом, Фиб(15) будет вычисляться два раза, Фиб(14) — три, Фиб(13) — 5, Фиб(12) — 8 раз и т.д. Всего при вычислении Фиб(17) понадобится более тысячи, при вычислении Фиб(31) — свыше миллиона, при вычислении Фиб(45) — свыше миллиарда операций сложения! (Кушниренко А.Г., Лебедев А.Г., Зайдельман Я.Н. Информатика 7–9: Учебник для общеобразовательных учебных заведений. М.: Дрофа, 2000). Для сравнения — при определении 45-го члена последовательности Фибоначчи по нерекурсивному варианту функции выполняется всего лишь 43 операции сложения.

Итак, учащиеся должны знать, что рекурсия — это, как правило, всегда эффектно, но не всегда эффективно…

---

¹ От лат. recursio — возвращение. — Прим. ред.
² Почему это важно, будет обсуждаться в разделе 2.
³ Обсуждение сопровождается графической иллюстрацией.
⁴ При изображении схемы на доске целесообразно соответствующий прямоугольник с нее стирать. Это же касается завершения работы функции F с другими фактическими параметрами. — Прим. ред.
⁵ Учащихся необходимо проинформировать, что во всех программах следует использовать рекурсию.
⁶ Данный раздел подготовлен редакцией. — Прим. ред.