Кандидат физико-математических наук, доцент факультета кибернетики Киевского национального университета имени Тараса Шевченко.

Рекурсия – одна из простейших концепций в алгоритмике. Суть рекурсии – сведение данной задачи к подобным, но более простым. Но не надо думать про рекурсию как про арифметику в математике. Несмотря на простоту идеи, иногда неясно, как практическую задачу свести к рекурсивной функции, какой у этой функции будет «физический смысл» и каким именно образом нужно осуществлять сведение. Часто альтернативным подходом рекурсии являются итерации, суть которых – повторение некоторой комбинации действий над хранимыми данными несколько раз. С первого взгляда итерации ещё примитивнее рекурсии, но, как это ни странно, на практике разрабатывать оптимальные итеративные алгоритмы сложнее, чем соответствующие им рекурсивные.

В этой статье рассмотрим ряд олимпиадных задач разной сложности, которые решаются при помощи итеративного и рекурсивного подходов.