Статья: Эмпирическое исследование времени выполнения рекурсивных функций и развитие STEM-компетенций*

В статье представлен подход к изучению рекурсивных функций на углубленном уровне освоения курса информатики в X—XI классах на примере функций вычисления факториала и обобщенных функций Фибоначчи различного порядка. Являясь объектом исследования в рассматриваемой в статье исследовательской работе, эти функции предоставляют усредненные экспериментальные данные времени выполнения, которые в дальнейшем визуализируются, анализируются и аппроксимируются. В процессе такого анализа соотносятся теоретические оценки вычислительной сложности и полученные экспериментальные данные времени выполнения рекурсивных функций в зависимости от переменных аргументов. Показаны примеры двумерной визуализации времени выполнения функции вычисления факториала средствами языка программирования Python и трехмерной визуализации времени выполнения обобщенных функций Фибоначчи различного порядка в редакторе электронных таблиц. Выделены развиваемые STEM-компетенции, изучаемые теории, методы, принципы и концепции в науке, технологиях, инженерии и математике. Объектами научной новизны в данной работе являются: демонстрация нелинейной вычислительной сложности рекурсивного алгоритма вычисления факториала в Python при больших аргументах и выявление причин такого поведения данного алгоритма, основанное на контрпримере; написание рекурсивной обобщенной функции вычисления чисел рядов Фибоначчи с различным порядком как пример реализации принципа DRY; предложенные подходы к углубленному изучению рекурсии и знакомству обучающихся с теорией вычислительной сложности.