Рекурсия – понятие не только математическое, или из области информатики, это понятие общее, философское. Оно встречается в литературе, искусстве, повседневной жизни. Правильное общее понимание этого термина поможет освоить его и применять в программировании и информатике. Важно, рассматривая рекурсивные определения объектов из разных областей науки и жизни, обратить снимание на их сходство: все определения состоят из рекурсивной части и нерекурсивной, базовой (именно эта часть позволяет в нужный момент закончить рекурсию).

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

Таким же образом дело обстоит и в программировании: один и тот же результат можно получить как с помощью рекурсивного алгоритма, так и помощью нерекурсивного. Какой алгоритм выбрать, какой лучше? Рекурсивные алгоритмы часто проще в написании, понятнее. Однако следует знать, что обычно рекурсивные вычисления требуют больше памяти и занимают больше времени. Именно поэтому большинство алгоритмов, которые предлагаются в учебниках по программированию при изучении рекурсии, – чисто учебные, они не являются более эффективными, чем «традиционные», нерекурсивные. Они не показывают преимуществ рекурсии, могут быть использованы лишь для демонстрации методов. К сожалению, в рамках школьного курса не так легко подобрать алгоритмы, при программировании которых использование рекурсии более эффективно, чем использование цикла. Классическим примером здесь является задача о ханойской башне (существует нерекурсивный алгоритм перестановки колечек, но он гораздо сложнее как для программирования, так и для понимания). Реже используемым, но тем не менее весьма показательным примером являются алгоритмы обработки последовательности, находящейся во входном файле (вводимой с клавиатуры). Простейшая задача: с клавиатуры вводится последовательность целых чисел, заканчивающаяся нулем, надо напечатать ее в обратном порядке. Для решения этой задачи с помощью циклического алгоритма придется завести массив, записать в него числа, затем их вывести. Но длина последовательности заранее неизвестна. Значит, придется заводить массив на всякий случай «побольше», то есть нерационально использовать память. Рекурсивный алгоритм (приведем его здесь на Паскале) лишен этих недостатков:

 Procedure Print;
  var a : integer;

 Begin read(a);

  If a=0 then Writeln

    else Begin

               Print

      Writeln(a);

     End

 End;

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

План построения узора может быть, например, таков: чертится геометрическая фигура заданного размера в центре экрана, затем та же фигура, но уже меньшего размера, чертится с центром в определенных местах первой фигуры (например, маленькие квадраты изображаются на серединах сторон большого «материнского» квадрата). Работа алгоритма (точнее, очередной рекурсивной ветви) заканчивается, когда размер изображаемой на данном шаге фигуры станет слишком маленьким. В качестве фигур можно использовать окружности, многоугольники, «звездочки», получаемые из диагоналей многоугольников. Изменяя параметры в такой программе, вставляя «задержки» при переходе от одной ветви рекурсии к другой, можно наблюдать за работой алгоритма, отслеживать активные и неактивные ветви. Таким образом, использование графики помогает наглядно продемонстрировать работу рекурсивных алгоритмов.