Читайте также:
|
Знакомство учащихся с понятием “рекурсия” и примерами использования ее в программировании является, безусловно, полезным, особенно при изучении информатики на профильном уровне. Рекурсия является удобным средством решения большого числа задач. Одна из них — задача нахождения 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 операции сложения.
Итак, учащиеся должны знать, что рекурсия — это, как правило, всегда эффектно, но не всегда эффективно…
Дата добавления: 2015-02-16; просмотров: 98 | Поможем написать вашу работу | Нарушение авторских прав |