Видеоурок «Рекурсивные алгоритмы. Быстрая сортировка элементов массива»

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

Урок начинается с краткого повторения материала о том, что такое вспомогательные алгоритмы и подпрограммы и их применении. Далее учащиеся переходят к определению рекурсивных алгоритмов.

Рекурсивные алгоритмы — это вспомогательные алгоритмы, которые в процессе своего исполнения вызывают сами себя.

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

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

Правило

Когда рекурсию можно заменить циклом — лучше так и поступить.

Причины:

• Использование рекурсии увеличивает расход оперативной памяти.
• Количество одновременных вызовов подпрограммы ограничено, и, если оно превысит допустимое, исполнение программы завершится ошибкой переполнения программного стека.

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