При изучении программирования многих учителей и учеников пугает слово «рекурсия». И действительно, эта тема является одной из самых сложных при изучении структурного программирования. При всём при этом ей не уделяется внимания в большинстве учебников информатики. Однако многие эффективные алгоритмы основаны именно на рекурсии, например, алгоритм быстрой сортировки. Этот урок поможет учащимся понять принцип работы рекурсивных алгоритмов: когда их использование необходимо, а когда его следует избегать.
Урок начинается с краткого повторения материала о том, что такое вспомогательные алгоритмы и подпрограммы и их применении. Далее учащиеся переходят к определению рекурсивных алгоритмов.
Рекурсивные алгоритмы — это вспомогательные алгоритмы, которые в процессе своего исполнения вызывают сами себя.
Многим ученикам это определение может показаться непонятным, поэтому на примере простейшей рекурсивной функции следует разъяснение принципа работы рекурсивных алгоритмов, а также разбор решения простой задачи с их использованием.
После того, как ученики получили представление о работе рекурсивных алгоритмов, рассматриваются ограничения, связанные с использованием таких алгоритмов, и их причины.
Правило
Когда рекурсию можно заменить циклом — лучше так и поступить.
Причины:
- Использование рекурсии увеличивает расход оперативной памяти.
- Количество одновременных вызовов подпрограммы ограничено, и, если оно превысит допустимое, исполнение программы завершится ошибкой переполнения программного стека.
Далее рассматривается один из наиболее эффективных алгоритмов сортировки, который основан на рекурсии — алгоритм быстрой сортировки элементов массива, а также принцип его работы и особенности реализации на языке Pascal.