 |
Некоторые понятия, связанные с рекурсией.
|
|
|
|
Место темы в предмете «Информатика и ИКТ»
Я предлагаю изучать данную тему в содержательной линии «Алгоритмизация и программирование» на профильном этапе непрерывного изучения информатики для профилей: физико-математический, естественнонаучный, информационно-технологический. Познакомить учащихся с рекурсивными алгоритмами можно на базовом этапе, после решения задач с использованием итерационных циклов или на вводном к базовому при изучении организации циклических алгоритмов с использованием языка ЛОГО.
Несмотря на то, что рекурсивные алгоритмы упоминаются в учебниках информатики, рекурсия для большинства школьников остается «таинственной незнакомкой». Еще бы! Примеров в учебнике явно недостаточно, да и те допускают очевидное решение с помощью обычного цикла. В то же время есть несколько классических задач, прекрасно иллюстрирующих возможности рекурсии. Это задачи о перестановках, размещении ферзей на шахматной доске, поиск пути в лабиринте, игра «Ханойские башни» и т. д. Следует сказать, что знакомство учащихся даже с простейшими рекурсивными алгоритмами (вычисления факториала натурального числа и квадрата натурального числа), предусмотренное в информатике, вызывает ряд трудностей в усвоении. Они обусловлены прежде всего сложностями структурно-логического характера в действиях, составляющих конструктивную основу таких алгоритмов. Естественно, подобные сложности и малый ресурс учебного времени не позволяют в процессе обучения на базовом этапе уделять достаточного внимание вопросам разработки рекурсивных алгоритмов решения задач.
Вместе с тем эффективность таких алгоритмов в сочетании с их идейным богатством и логикой построения служат отправными моментами для включения в олимпиады по информатике задач, в основу решения которых положена рекурсия. Понятно, что для успешного решения подобных задач участники олимпиад должны кроме понимания сущности рекурсивных алгоритмов иметь также и определенный опыт их разработки, который не может дать разбор приведенных в учебном пособии задач.
|
|
|
Понятие рекурсии.
Слово рекурсия происходит от латинского слова recursion – возвращение.
Объект называется рекурсивным, если он содержит сам себя или определен с помощью самого себя. Рекурсивные определения как мощный аналитический аппарат используются во многих областях науки, особенно в математике.
Например:
1.Натуральные числа:
(а) 1 есть натуральное число;
(в) целое число, следующее за натуральным, есть натуральное число.
\==^^
2.Функция факториал (n!) для неотрицательных целых чисел:
(а) 0!=1
(в) если n>0, то n! =n*(n-1)!
3.Числа Фибоначчи;
(1) F(l)=l
(2) F(2)=1
(3) для V n>2 F(n)=F(n-1)+F(n-2)
Определение рекурсивного алгоритма и рекуррентных соотношений.
Одни из наиболее эффективных приемов, используемых при разработке алгоритмов решения ряда задач, является применение вспомогательных алгоритмов (подпрограмм). Вспомогательные алгоритмы – это алгоритмы, используемые в качестве составных частей в основном алгоритме.
С понятием вспомогательного алгоритма связано более сложное понятие – рекурсивный а лгоритм, то есть алгоритм, использующий в качестве вспомогательного самого себя. Если процедура Р содержит явное обращение к самой себе, то она называется прямо рекурсивной; если Р содержит обращение к процедуре Q, которая содержит (прямо или косвенно) обращение к Р, то Р называется косвенно рекурсивной.
Основой для разработки рекурсивных алгоритмов служат так называемые рекуррентные соотношения. Эти соотношения связывают значения искомой функции от некоторого натурального аргумента со значением этой же функции от предыдущего по величине аргумента, а также задают прямое правило определения значения функции для минимального значения аргумента.
|
|
|
Почему изучают рекурсию?
1. Рекурсия представляет собой одно из полезных средств в инструментальном оснащении программиста.
2. Рекурсивный алгоритм короче и проще итеративного.
3. Самостоятельная реализация рекурсивного алгоритма позволяет глубже разобраться в механизме исполнения и в назначении вспомогательного алгоритма.
Но можно привести несколько доводов и против применения рекурсивной программы:
1) На большинстве машин рекурсивная программа выполняется существенно медленнее, чем не рекурсивная из-за расходов времени, связанных с организацией стека для адресов возврата и для организации стеков для хранения значений локальных переменных. С рекурсивной процедурой связано некоторое множество локальных объектов: переменных, констант, типов, процедур, которые определены локально внутри этой процедуры, а вне ее не существуют или не имеют смысла. Каждый раз, когда такая процедура рекурсивно вызывается, для нее создается новое множество локальных переменных. Хотя они имеют те же имена, что и соответствующие элементы множества локальных переменных, созданных при предыдущем обращении к этой процедуре, их значения различны.
2) В силу того, что большинство учащихся не достаточно глубоко понимают механизм исполнения рекурсивных алгоритмов, отладка программы, если она содержит ошибки, весьма затруднительна, особенно если используется глубокая рекурсия.
Нельзя рекомендовать применять рекурсию повсеместно. Необходимо оценить, насколько целесообразно облегчить работу по написанию программы, подвергая себя при этом опасности усложнить отладку и увеличить время счета. Алгоритм, описанный рекурсивно, выглядит очень просто, однако работает этот алгоритм весьма неэкономично. Например, для нахождения 17 члена последовательности Фибоначчи необходимо выполнить свыше одной тысячи операций, 31 – свыше миллиона, 45 – свышемиллиарда операций сложения. А по итеративному, например, для вычисления 45 – го члена последовательности Фибоначчи выполняется всего лишь 45 операций сложения.
|
|
|
Некоторые понятия, связанные с рекурсией.
Максимальное число рекурсивных вызовов процедуры без возврата, которое происходит во время выполнения программы, называется глубиной рекурсии. Число рекурсивных вызовов в каждый конкретный момент времени, называется текущим уровнем рекурсии. Переменная, управляющая рекурсией, называется параметром рекурсии.
Рекурсивная подпрограмма состоит из 2 частей: первая часть реализует спуск до наименьшего значения параметра рекурсии; вторая часть -рекурсивный подъем.
Подобно операторам цикла, рекурсивные процедуры могут привести к бесконечным вычислениям. Поэтому необходимо рассмотреть проблему окончания работы процедур. Очевидно, что для того, чтобы работа рекурсивной программы когда-то завершилась, необходимо, чтобы рекурсивное обращение к процедуре Р подчинялось условию В, которое в какой-то момент перестает выполняться.
Программы, в которых используются рекурсивные процедуры, отличаются простотой, наглядностью и компактностью текста. Такие качества рекурсивных алгоритмов вытекают из того, что рекурсивная процедура указывает, что нужно делать, а не рекурсивная больше акцентирует внимание на том, как нужно делать. Однако за эту простоту приходиться расплачиваться неэкономным использованием оперативной памяти, так как выполнение рекурсивных процедур требует значительно большего размера оперативной памяти во время выполнения, чем не рекурсивных.
|
|
|
