Рекурсия в алгоритме будет косвенной когда
Главное меню
Соглашение
Регистрация
Английский язык
Астрономия
Белорусский язык
Информатика
Итальянский язык
Краеведение
Литература
Математика
Немецкий язык
Обществознание
Окружающий мир
Русский язык
Технология
Физкультура
Для учителей
Дошкольникам
VIP — доступ
Автор: Гайнанова Эльвина Назимовна | ID: 9292 | Дата: 21.3.2017
Помещать страницу в закладки могут только зарегистрированные пользователи
Зарегистрироваться
Получение сертификата
о прохождении теста
Рекурсия — Python: Функции
В этом уроке мы узнаем, что такое рекурсия, зачем она нужна и чем отличается рекурсия в математике и в языках программирования. Еще мы разберем условие завершения рекурсии и обсудим, какие виды рекурсии существуют.
Что такое рекурсия
Рекурсия в программировании — это возможность дать определение функции, используя в процессе саму определяемую функцию. В математике многие функции определены именно таким образом, поэтому и большинство языков программирования используют этот подход.
Это работает и в Python. Обычно в определении функции можно использовать только определения, которые дали ранее. Но есть одно исключение — функция в своем теле может вызывать себя. Выглядит это так:
def factorial(n): if n 0: return 1 return n * factorial(n - 1) Интерактивный пример: https://replit.com/@hexlet/python-functions-recursion-factorial#main.py
Эта функция вычисляет факториал числа n через умножение числа на факториал числа n — 1 .
Условие завершения рекурсии
В примере выше используется условие, которое прекращает рекурсию. Если в этой функции убрать условие, которое проверяет аргумент на неотрицательность, то первый же вызов этой функции заставит программу зациклиться — функция продолжит вызывать себя постоянно.
В определениях рекурсивных функций практически всегда есть подобное условие. Оно позволяет вычислению пойти по одной из веток:
- По рекурсивной — в этой ветке произойдет вызов себя
- По терминальной — закончит вычисление и вернет результат
Какой-то из аргументов рекурсивной функции должен обязательно убывать. В качестве убывания может быть:
- Уменьшение счетчика
- Отбрасывание головы списка при движении к его хвосту
- Вызов себя для части исходной структуры при обработке древовидных структур данных
Чтобы понять, что программа не зациклится, используют метод «пристального взгляда» и тесты. Особенно важно проверять срабатывание условия завершения рекурсии.
Переполнение стека
В большинстве программ, написанных на поддерживающих вызов функции языках, этот вызов устроен так: перед вызовом функции текущее место в программе запоминается в стеке. А когда функция возвращает результат, то соответствующий элемент стека отбрасывается.
Стек (stack) — это абстрактный тип данных, который похож на стопку монет. Монета, которую положили последней, будет снята первой. И при снятии монет порядок получается обратным порядку складывания.
В этом же стеке сохраняются значения аргументов функции, а иногда и другая служебная информация. При этом память, которая выделяется для стека при запуске программы, конечна и ограничена.
Если функция будет вызывать себя постоянно и не возвращать результат, то память в итоге закончится. Когда заканчивается память, выделенная для стека вызовов, стек переполняется.
В итоге мы не сможем посчитать факториал для достаточно больших чисел с помощью рекурсивной функции. Но сможем посчитать с помощью итеративной — написанной с использованием циклов и переменных.
Так выглядит переполнение стека при подсчете факториала:
factorial(1000) # Traceback (most recent call last): # File "", line 1, in # File "", line 4, in factorial # File "", line 4, in factorial # File "", line 4, in factorial # [Previous line repeated 995 more times] # File "", line 2, in factorial # RecursionError: maximum recursion depth exceeded in comparison Сообщение говорит, что превышена максимальная глубина рекурсии. Глубиной рекурсии называется количество последовательных вызовов себя без возврата значения. В Python максимальная длина искусственно ограничена, потому что проще считать количество вызовов, чем предсказывать окончание памяти.
Зачем нужна рекурсия
Некоторые алгоритмы реализуются проще, если использовать именно рекурсию, а не циклы. Часто такие алгоритмы работают с рекурсивными структурами данных — деревьями, «словарями словарей словарей» и подобными. При реализации таких алгоритмов нужно помнить, что память для стека конечна. При этом обычно конечны и сами обрабатываемые структуры данных, поэтому отказываться полностью от рекурсии не стоит.
Виды рекурсии
Рекурсии можно разделить на два вида по тому, как они себя вызывают:
- Прямая — когда функция вызывает себя
- Косвенная — когда одна функция внутри себя вызывает другую функцию, которая когда-то вызовет первую
Так же рекурсии можно разделить по количеству рекурсивных вызовов:
- Линейная — когда при вычислении результата функции функция вызывает себя один раз, как в примере с factorial . Уточним, что «один раз» — это не про общее количество вызовов функции в теле. Речь идет о количестве вызовов, результаты которых нужны для одного общего вычисления
- Каскадная — когда функция вызывает себя несколько раз
Рассмотрим подробнее линейную и каскадную рекурсию.
Пример линейной рекурсии
Если рекурсия в функции проверяет Гипотезу Коллатца , она считается линейной:
def collatz(n): if n == 1: return True if n % 2 == 0: return collatz(n // 2) return collatz(n * 3 + 1) Интерактивный пример: https://replit.com/@hexlet/python-functions-recursion-collatz#main.py
Здесь в теле функции есть два рекурсивных вызова, но в каждом заходе используется только один.
Еще один пример использования линейной рекурсии — обход коллекций. Для этого можно рекурсивно представить коллекцию как:
- Начало (голову)
- Остальную часть коллекции (хвост)
Дальше хвост также можно разложить на голову и новый хвост. И так до тех пор, пока не останется голова и пустой хвост:
[1, [2, 3]] -> [1, [2, [3]]] -> [1, [2, [3, []]]]
При рекурсивной обработке коллекции мы будем обходить коллекцию и дробить старый хвост на новую голову и новый хвост на каждой итерации. Так мы делаем до тех пор, пока не получим пустой хвост — то есть конец коллекции:
# Функция рекурсивно обходит список, суммируя числа из него def sum(array): # Мы можем использовать оператор упаковки для записи в хвост остальной части списка head, *tail = array if not tail: return head return head + sum(tail) Пример каскадной рекурсии
Если рекурсия в функции вычисляет очередное Число Фибоначчи , она называется каскадной:
def fibonacci(n): if n 2: return 1 return fibonacci(n - 1) + fibonacci(n - 2) Интерактивный пример: https://replit.com/@hexlet/python-functions-recursion-fibonacci#main.py
Здесь функция всегда вызывает себя два раза. Сначала будет два вызова, которые превратятся в четыре — два раза по два вызова. Затем в восемь — количество вызовов растет каскадно.
Открыть доступ
Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно
- 130 курсов, 2000+ часов теории
- 1000 практических заданий в браузере
- 360 000 студентов
Наши выпускники работают в компаниях:
Что такое рекурсия?
Процесс, в котором функция вызывает себя прямо или косвенно, называется рекурсией. Эта функция называется рекурсивной функцией. Используя рекурсивный алгоритм, некоторые задачи могут быть решены довольно легко.
Обновлено: 2022-07-23 15:16:58 КК Константин Кондрусин автор материала
Что такое рекурсия- основное условие в рекурсии
В рекурсивной программе предлагается решение основного случая, а решение более крупной задачи выражается в условиях меньших задач:
int fact(int n) < if (n < = 1) // основной случай return 1; else return n*fact(n-1); >
Почему ошибка переполнения стека происходит в рекурсии?
В рекурсивной процедуре и функции если основной случай не достигнут или не определен, может возникнуть проблема с переполнением стека. Давайте посмотрим на примере, чтобы понять:
int fact(int n) < // неправильный основной случай (это может вызвать // переполнение стека). if (n == 100) return 1; else return n*fact(n-1); >
Если вызывается рекурсивная функция C fact (10) , она будет вызывать fact (9) , fact (8) , fact (7) и т. д. Но переменная никогда не достигнет значения 100 . Таким образом, конечный вариант не достигается. Если память исчерпана функциями в стеке, это вызовет ошибку переполнения стека.
В чем разница между прямой и косвенной рекурсиями?
Функция fun называется прямой рекурсивной, если она вызывает ту же функцию fun . Функция fun называется косвенной рекурсивной, если она вызывает другую функцию. Разница между прямой и косвенной рекурсией проиллюстрирована в коде ниже:
// Пример прямой рекурсии void directRecFun() < // Какой-то код. directRecFun(); // Какой-то код. >// Пример косвенной рекурсии void indirectRecFun1() < // Some code. indirectRecFun2(); // Some code. >void indirectRecFun2() < // Какой-то код. indirectRecFun1(); // Какой-то код. >
В чем разница между хвостовой и не хвостовой рекурсиями?
Для понимания рекурсивной функции важно знать об этом различии. Функция является хвостовой, когда рекурсивный вызов является последним, выполняемым функцией.
Как распределена память для разных вызовов функций в рекурсии?
Когда функция вызывается из main() , ей выделяется память в стеке. Рекурсивная функция вызывает себя. Память для вызываемой функции выделяется поверх памяти, выделенной для функции вызова. Для каждого вызова функции создается отдельная копия локальных переменных. Когда конечный вариант достигнут, функция возвращает свое значение функции, которой она вызвана, память освобождается, и процесс продолжается.
Приведем пример, когда рекурсия работает, выполняя простую функцию:
// в программе на C++ показывается работа // рекурсии #include using namespace std; void printFun(int test) < if (test < 1) return; else < cout > int main()
Когда printFun(3) вызывается из main() , память присваивается printFun(3) , а локальная переменная test инициализируется значением 3 . При этом выражения 1 — 4 помещаются в стек, как показано на диаграмме, представленной ниже. Сначала выводится « 3 ». Во втором выражении вызывается printFun(2) и память присваивается printFun(2) , а локальная переменная test инициализируется значением 2 , а выражения 1 — 4 помещаются в стек. Аналогично, printFun(2) вызывает printFun(1) и printFun(1) вызывает printFun(0) . printFun(0) переходит в fact if , и возвращается к printFun(1) . Остальные выражения printFun(1) выполняются и возвращаются к printFun(2) и так далее. Выводятся значения от 3 до 1 , а затем печатаются от 1 до 3 . Стек памяти рекурсивной функции показан на диаграмме, приведенной ниже:
Каковы недостатки рекурсивного программирования по сравнению с итеративным программированием?
Как рекурсивные, так и итеративные программы обладают одинаковыми способностями решения задач. То есть, каждая рекурсивная программа может быть записана итеративно и наоборот. Рекурсивная программа предъявляет больше требований к используемой памяти, чем итеративная, поскольку в ней все функции остаются в стеке до тех пор, пока не будет достигнут оптимальный вариант.
Рекурсия также занимает больше времени из-за вызовов функций и издержек на возврат.
Каковы преимущества рекурсивного программирования над итерационным программированием?
Рекурсия обеспечивает простой и понятный способ написания кода. Некоторые задачи являются неотъемлемо рекурсивными. Для них предпочтительнее использовать рекурсивный код. Подобный код можно писать итеративно с помощью структуры данных « стек ».
Материалы к урокам по теме «Рекурсивные алгоритмы»
Алгоритм называется “рекурсивным” 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.
Любое рекурсивное определение состоит из двух частей. Эти части принято называть “базовой” и “рекурсивной”. Базовая часть является нерекурсивной и задает определение для некоторой фиксированной части объектов. Рекурсивная часть определяет понятие через него же и записывается так, чтобы при цепочке повторных применений она сводилась бы к базовой части 2 .
Так и, разрабатывая программу, часто удается свести исходную задачу к более простым задачам. Среди них может оказаться и первоначальная задача, но в упрощенной форме. Например, вычисление функции 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;
Readkey
End;
BEGIN
Print
END.
Учитель: “Сколько раз текст истории будет выведен на экран?”.
В ходе обсуждения необходимо рассказать (напомнить), что при каждом вызове вспомогательной процедуры (функции) для нее отводится место в оперативной памяти, которое “освобождается” после завершения ее (процедуры) работы. Но если во вспомогательной процедуре имеется рекурсия, то вызовы вспомогательных процедур будут продолжаться до тех пор, когда выделенное место в памяти будет исчерпано (в результате на экране появится сообщение об ошибке, связанной с этим фактом) 3 .
Чтобы устранить этот недостаток, необходимо так оформлять процедуры (функции), чтобы рекурсивные вызовы осуществлялись по условию, которое когда-то станет ложным.
Например, в рассмотренной программе должна быть описана процедура с параметром и использован условный оператор:
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 и ей будет передано значение n = 2. При выполнении функции также “сработает” рекурсивная ветвь:
что потребует очередного размещения в памяти функции F с параметром n = 1. При ее выполнении рекурсивного вызова не будет (согласно базовой части F = 1). Найденное значение F(1) = 1 будет передано в функцию, откуда была вызвана функция F с параметром n = 1, после чего место, выделенное под последнюю функцию, освободится 4 . В результате будет рассчитано значение 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
If a >= p Then From10(a div p, p);
remin := a mod p;
write(remin)
End;
От редакции. Последний вариант рекурсивной процедуры называется “Форма с выполнением действий после рекурсивного вызова (или с выполнением действий на рекурсивном возврате)”. Возможны также форма с выполнением действий до рекурсивного вызова (или с выполнением действий на рекурсивном спуске) и форма с выполнением действий как до, так и после рекурсивного вызова (или с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате) — см. Златопольский Д.М. Программирование: типовые задачи, алгоритмы, методы. М.: БИНОМ. Лаборатория знаний, 2007. Схемы этих трех вариантов и примеры их применения приведены в разделе 5 .
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;
Begin
If n mod d = 0 Then
Begin
write(d, ‘ ‘);
dd := n div d;
If d <> dd Then
Begin
Dived(n, d + 1);
write(dd, ‘ ‘)
End
End
Else 0>
Dived(n, d + 1)
End;
Вызов процедуры из основной программы осуществляется следующим образом:
От редакции. Здесь используется форма рекурсивной процедуры с выполнением действий как до, так и после рекурсивного вызова (или с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате).
6. Процедура получения и вывода на экран всех вариантов разложения заданного натурального числа n на множители (без повторений).
Решение будем получать в строковом виде, аналогичном следующему (для n = 12):
Можем рассуждать так. Проверим все числа, которые могут быть множителями числа 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, решающая задачу:
Вызов разработанной процедуры из основной части программы должен выглядеть следующим образом: R(n, 2, ») ;
После обсуждения программы целесообразно предложить учащимся проследить последовательность рекурсивных вызовов процедуры R.
От редакции. В приведенном виде процедуры последнее разложение будет представлять собой строковое представление числа n (без множителя, равного 1), например, для случая n = 12: 12. Для получения вида, аналогичного следующему: 1*12, необходимо:
1) последний фрагмент процедуры оформить в виде:
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-ичной системе является четырехзначным (а3а2а1а0), то десятичное значение этого числа определяется следующим образом:
Функция, “работающая” по этой схеме, может иметь вид:
Function RevTo10(S: string; p: byte): longint;
Var last: byte; code: integer; Begin
If length(S) = 1 Then
Begin
Val(S[Length(S)], last, code);
RevTo10 := last
End
Else
Begin
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;
Begin
Val(S, k, code);
If k < 10 Then RevTo10 := k
Else
Begin
last := k mod 10;
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;
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;
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(n div 10);
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;
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(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 And (j mod k <> 0) Do k := NextPrim(k);
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. Формы рекурсивных процедур 6
В общем случае любая рекурсивная процедура Р включает в себя некоторое множество операторов Д и один или несколько операторов рекурсивного вызова Р. Структура рекурсивных процедур может принимать три разных формы.
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(арг цел a)
нач
если a > 1
то
П1(a — 1)
все
вывод a * а, » »
кон
алг П2(арг цел a)
нач
если a > 0
то
П2(a — 1)
вывод –a, » »
все
кон
Ответ: при n = 5: –1 –2 –3 –4.
алг П3(арг цел a)
нач
вывод 2 * a, » »
если a > 1
то
П3(a — 1)
все
кон
алг П4(арг цел a)
нач
если a > 0
то
вывод a * а * а, » »
П4(a — 1)
все
кон
Ответ: 64 27 8 1.
алг П5(арг цел a)
нач
вывод a * a
если a > 1
то
П5(a — 1)
все
вывод a * а, » »
кон
Ответ: 16 9 4 1 1 4 9 16.
алг П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 операции сложения.
Итак, учащиеся должны знать, что рекурсия — это, как правило, всегда эффектно, но не всегда эффективно…
1 От лат. recursio — возвращение. — Прим. ред.
2 Почему это важно, будет обсуждаться в разделе 2.
3 Обсуждение сопровождается графической иллюстрацией.
4 При изображении схемы на доске целесообразно соответствующий прямоугольник с нее стирать. Это же касается завершения работы функции F с другими фактическими параметрами. — Прим. ред.
5 Учащихся необходимо проинформировать, что во всех программах следует использовать рекурсию.
6 Данный раздел подготовлен редакцией. — Прим. ред.