Понятие рекурсии

Рекурсия — это жемчужина теории алгоритмов. Это первое, с чем знакомят школьников, после того, как они овладеют процедурами ввода и вывода данных, элементарными арифметическими операциями, оператором цикла и условного оператора. Простота рекурсии обманчива. Она таит в себе множество ловушек и сложных моментов, но и преподносит много подарков.

Давно известен такой математический приём, как сведение задачи к нескольким более простым. Затем простые задачи можно снова свести к ещё более простым и так далее, пока не доберёмся до самых элементарных задач.

Представьте, что нужно пройти 1000 шагов. Для решения этой задачи вы делаете один шаг, и остаётся 999 шагов. Таким образом, задача упростилась. Сделав такое упрощение 999 раз, дойдём до самой элементарной задачи — сделать один шаг. Конечно, этот пример слишком прост. Далее мы рассмотрим несколько более сложных примеров, поясняющих идею рекурсии и демонстрирующих её хорошие и плохие стороны.

Прежде всего важно заметить аналогию рекурсии с понятием математической индукции. У рекурсии, так же как и в методе математической индукции, есть база — аргументы, для которых значения функции определены (элементарные задачи), и шаг рекурсии — способ сведения данной задачи к более простым задачам (тем, которые мы уже умеем решать).

В статье описывается старинная головоломка, русский вариант которой известен под названием «меледá». Решение этой головоломки

тесно связано с информатикой. Здесь и первое в истории, по нашему мнению, практическое использование двоичной системы счисления,

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