7.1. Цикл, итерация, рекурсия

7. Алгоритмы

Алгоритмы, которые мы до сих пор рассматривали, можно назвать очевидными (Оче-Видными ☺), их поведение умозрительно наблюдается на образной модели, задача программиста – увидеть его составные части и выстроить их в нужной последовательности. Составные части таких алгоритмов разнородны, а процесс их выполнения можно отследить «исторически». Однако есть и другие подходы проектированию, кроме образной очевидности. Скажем о них самыми общими словами:

• алгоритмы, последовательно приближающиеся к заданной цели;

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

• алгоритмы, соблюдающие установленные для них соотношения (свойства, «законы», инварианты);

Соответственно, меняется и технология их разработки: основной задачей является – направить алгоритм «в нужное русло», заставить двигаться его в нужном направлении, соблюсти «правила игры», правильно свести задачу к аналогичной. Очевидность и наблюдаемость здесь уступают место логической непротиворечивости и доказательности соблюдения программой заданных свойств.

Цикл, итерация, рекурсия. В главе 3.7 мы уже обсуждали «хорошие» и «плохие» циклы. «Хороший цикл» состоит из независимых частей и его тело не влияет на условия его выполнения. Еще более тесно связаны между собой части итерационного цикла – в нем результат текущего шага зависит от нескольких предыдущих. Здесь мы имеем последовательность взаимосвязанных шагов. Аналогично можно ввести понятие последовательности (а также и разветвляющейся последовательности) алгоритмов (функций), в которой каждый шаг (алгоритм) определяет начальные условия выполнения аналогичных алгоритмов и использует их результаты. Это и есть определение рекурсии.

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

Рекурсия в жизни, литературе, искусстве

Примеры рекурсии можно встретить в литературе, искусстве, фольклоре.

«У попа была собака, он ее любил. 
Она съела кусок мяса, он ее убил. 
Камнем придавил, и на камне написал: 
«У попа была собака...»» (Детская считалка) 

Я хочу Вам написать, что я хочу Вам написать, что я хочу Вам написать ... 
(из письма пациента психиатру) 

«Я знаю, что ты знаешь, что я знаю» 
(кинокомедия Альберто Сорди, Италия, 1982). 

«Я оглянулся посмотреть,
не оглянулась ли она,
чтоб посмотреть, не оглянулся ли я...»
(Максим .Леонидов, «Девочка-видение», песня).

В тамбуре, пуская дым в окошко, Монахов на некоторое время обрел пространство: мусорный ящик, огнетушитель, декларация какая-то под стеклом, дверь в туалет, плевок – все на месте. Давно пора было закурить… подчеркнуто выпустил дым – отлегло. Что это все на него находит? Благожелательно приласкал взглядом огнетушитель: на месте, друг! Не действуешь?.. И то, что на огнетушителе была картинка, на которой человек, успев переодеться в комбинезон, правильно держал в руках точно такой же огнетушитель, на котором, в свою очередь, была картинка, на которой… это, с детства запавшее представление, тут же тысячу раз проигранное в мозгу, не было почему-то ему противно, наоборот: усмехнулся себе ласково, будто подмигнул прошлому… (Андрей Битов. “Вкус”).

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

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

В программировании таких примеров еще больше:

• определение любого конкретного оператора (условный, цикл, блок) в качестве составных частей включает произвольный оператор;

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

• рекурсивная функция - тело функции содержит прямой или косвенный (через другую функцию) собственный вызов.

Рекурсивные алгоритмы и функции и их свойства

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

Линейная рекурсия. Простейшим примером рекурсии является линейная рекурсия, когда функция содержит единственный условный вызов самой себя. В таком случае рекурсия становится эквивалентной обычному циклу. Действительно, любой циклический алгоритм можно преобразовать в линейно-рекурсивный и наоборот.

//----- Циклический алгоритм вычисления факториала
int fact(int n) {
  for (int s=1; n!=0; n--) s *=n;
  return s;
}

//------ Рекурсивный алгоритм вычисления факториала
int fact(int n) {
  if (n==1) return 1;
  return n * fact(n-1); 
}

Приведенный пример не демонстрирует каких-то особенных преимуществ линейной рекурсии. Тем не менее, линейная рекурсия элегантно смотрится на линейных структурах данных – односвязных списках.

//--- Включение в односвязный с сохранением порядка – циклическая программа
// pr - указатель на предыдущий элемент списка
void InsSort(list *&ph, int v) { 
  list *q ,*pr,*p; q=new list; q->val=v;

  // перед переходом к следующему указатель на текущий
  // запоминается как указатель на предыдущий

  for ( p=ph,pr=NULL; p!=NULL && v>p->val; pr=p,p=p->next);
  if (pr==NULL) { // включение перед первым 
    q->next=ph; ph=q; 
  } else { // иначе после предыдущего 
    q->next=p; // следующий для нового = текущий
    pr->next=q; // следующий для предыдущего = новый 
  }
}                          

//--- Рекурсивное включение в односвязный список с сохранением порядка
void InsSort(list *&ph, int v) {
  if (ph==NULL || v < ph->val) { // включение, если последний или если
    list *pp=new list; // меньше следующего
    pp->val=v;
    pp->next=ph;
    ph==pp; // ради присваивания по ссылке - рекурсия
  } else InsSort(ph->next,v); // иначе – рекурсивный вызов для следующего
}

Особенность включения в односвязный список – указатель на новый элемент должен быть помещен в предыдущий элемент списка, указатель на который программа должна «помнить». Рекурсия позволяет использовать ссылку на указатель для любого элемента списка.

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

//---- Ветвящаяся рекурсия
void F1() {
  …if () F1(); // Не более 2 рекурсивных вызовов
  …if () F1();
}

void F2() {
  …if ()
  for (int i=0;i<m;I++) F2(); // Рекурсивный вызов в цикле
}

Все приведенные выше литературно-художественные примеры имеют отношение к линейной рекурсии. Для ветвящейся рекурсии есть только одна физическая аналогия – цепная реакция: каждый рекурсивный вызов порождает n себе подобных. В структурах данных аналогичная «конструкция» называется деревом.

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

void main() {     void F() {       void F() {       void F() { 
  F();              ..if() F();      ...if() F();     ...if() F(); 
}                 }                }                } 

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

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

• в стеке резервируется место для формальных параметров, в которые записываются значения фактических параметров. Обычно это производится в порядке, обратном их следованию в списке;

• при вызове функции в стек записывается точка возврата - адрес той части программы, где находится вызов функции;

• в начале тела функции в стеке резервируется место для локальных (автоматических) переменных.

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

Рекуррентные соотношения

Рекуррентные соотношения определяют некоторый элемент последовательности через несколько предыдущих. Например, числа Фибоначчи: F(n)=F(n-1)+F(n-2), где F(0)=1, F(1)=1. Если рассматривать этот ряд от младших членов к старшим, способ его построения задается итерационным циклическим алгоритмом.

//  Вычисление чисел Фибоначчи итерационным методом
// F2 – «позавчерашнее» значение ряда
// F1 – «вчерашнее» значение ряда
// F0 – «сегодняшнее» значение ряда

int FIBO(int n) {
  int F2=1,F1=1,n=1;
  for (int i=0; i < n; i++) {
    F0=F1+F2;
    F2=F1,F1=F0; // при переходе к следующему шагу текущий становится
  } // предыдущим
}

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

//  Рекурсивное вычисление чисел Фибоначчи
int FIBO(int n) {
  if (n>=1) return 1;   // Для первых двух членов ряда - 1
  return F(n-1)+F(n-2); // Результат – сумма рекурсивно вычисленных значений
}

Трудоемкость рекурсивных алгоритмов

Трудоемкость – это зависимость времени выполнения алгоритма от размерности входных данных. В рекурсивных функциях размерность входных данных определяет глубину рекурсии. Если имеется ветвящаяся рекурсия – цикл из m повторений, то при глубине рекурсии N общее количество рекурсивных вызовов будет порядка N^m, поскольку с каждым шагом рекурсии оно увеличивается в m раз. Показательный характер функции говорит о том, что трудоемкость рекурсивных алгоритмов значительно превышает трудоемкость известных нам алгоритмов сортировки и поиска. Для различных случаев рекурсивных алгоритмов, когда задача размерности n сводится к задаче меньшей размерности (обычно n/2 или n-1) и при этом содержит определенное количество операций, кратное текущей размерности 1 или n, результирующие значения трудоемкости несложно оценить.