Рекурсия

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

Другими словами, рекурсия — частичное определение объекта через себя, определение объекта с использованием ранее определённых. Рекурсия используется, когда можно выделить самоподобие задачи.

Определение в логике, использующее рекурсию, называется индуктивным (см., например, Натуральное число).

Рекурсия в программировании

В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.

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

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

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

Описание типа данных может содержать ссылку на саму себя. Подобные структуры используются при описании списков и графов. Пример описания списка (C++):

class element_of_list; /* необходимо по правилам C++ */

class element_of_list

{ element_of_list *next; /* ссылка на следующий элемент того же типа */

int data; /* некие данные */};

Рекурсивная структура данных зачастую обуславливает применение рекурсии для обработки этих данных.

Наследование интерфейса - обязательство реализации реализовать не только "свои" методы, но и методы базовых абстрактных классов. Как она будет это делать - декларацию интерфейса не касается. Но очевидно, что каждому методу интерфейса-наследника (и всех методов базовых интерфейсов в него входящих) следует определить реализующий метод обычного класса. Т.е. реализация наследования интерфейсов может быть сделана только путём включения и не может быть сделана путём агрегирования, поскольку на этапе компиляции компилятор заявит, что увидел абстрактный метод, которому в данном коде он не нашёл реализации.

Когда какой способ наследования следует применять? Если интерфейсы X и Y связаны синтаксически, т.е. методы X не имеют никакого смысла без того, чтобы ранее не были определены методы Y, и это обстоятельство не зависит от реализации (т.е. любая реализация будет вынуждена поступать именно так и никак иначе), то в данном случае имеет место быть наследование интерфейса. Требование COM, чтобы всякий интерфейс реализовывал в себе IUnknown есть хороший тому пример - всякий интерфейс обязан наследовать интерфейсу IUnknown, каким бы образом он ни реализовывался.

Если же, напротив, интерфейсы X и Y связаны семантически, т.е. смыслом именно такой, а не какой-то иной реализации, то в данном случае имеет место быть наследование реализации. В каком виде: в виде агрегирования или в виде включения - зависит от обстоятельств. Технических, маркетинговых или иных. Теоретически, оба способа имеют равные выразительные возможности, но несколько разнятся по предъявляемому результату. Например, если базовый интерфейс экспонирует десять методов, а вам в интерфейсе-наследнике следует показать клиенту только один из них, то, вероятно, включение будет более предпочтительным способом, нежели агрегирование - хотя бы из тех соображений, что клиенту не стоит показывать лишнего.

Наследование интерфейсов

В Office 2000 на классах введено отношение "наследование интерфейса" . Здесь под интерфейсом понимается совокупность всех открытых (Public) свойств и методов класса. Пусть уже создан класс A, который будем называть родительским или базовым. Тогда при создании нового класса B, который будем называть классом-потомком, можно объявить, что потомок наследует интерфейс родительского класса. Заметьте, что это отношение в отличие от "классического" наследования не транзитивно, - потомок класса B не наследует интерфейс класса A - родителя класса B. Однако допускается множественное наследование интерфейсов, потомок может иметь несколько родителей, - наследовать интерфейсы нескольких классов. Говоря о родительском классе, следует отметить три возможности:

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

• Родительский класс может быть полностью определенным классом с заданной реализацией методов.

• Зачастую, родительский класс является абстрактным классом, где часть методов, реализация которых предполагается одинаковой для большинства классов - потомков, задана, а некоторые методы являются чистыми.

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

Implements имя_родительского_класса

П ри появлении такой строки класс- потомок наследует интерфейс родительского класса. Это означает, что будут наследоваться все открытые методы, а для каждого открытого свойства, будет наследоваться пара процедур - свойств Property Get и Property Let. Сами свойства наследоваться не будут. Как только в раздел объявлений класса вставлена строка "Implements", в окне кода этого класса появится список методов родительского класса, реализацию которых предстоит написать. Для того чтобы задать реализацию этих методов, используется привычная техника первоначального создания заготовок методов с последующим наполнением их содержательным текстом.

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

• Наследование интерфейса. Объект-потомок наследует у родителя его интерфейс, возможно, пополняя его новыми методами. Однако потомок не использует никакой функциональности предка и вынужден самостоятельно реализовывать все методы. Такое наследование допускает возможность автоматического преобразования типа от потомка к предку и создание иерархии типов. Наличие подобной иерархии позволяет уменьшить количество интерфейсов в системе и упростить ее структуру.

• Наследование функциональности. Потомок наследует не только интерфейс, но и код методов. Такое наследование имеет принципиальное значение для повторного использования кода.

• Наследование состояния. Для того чтобы использовать функциональность методов предка для потомка, необходимо, чтобы структура данных потомка содержала все поля данных предка. Наследование функциональности обычно требует использования наследования состояния, поэтому эти два типа наследования можно объединить в один - наследование реализации. Такой механизм наследования используется для объектов в большинстве современных языков программирования, в том числе, в C++ и Java [1]. Однако в распределенных системах наследование почти никогда не применяется.

Так вот, язык позволяет унаследовать класс от другого класса, потенциально содержащего реализацию. НО ТОЛЬКО ОТ ОДНОГО! Поясню, зачем это сделано. Дело в том, что каждая реализация может иметь дело только со своей частью - с теми переменными и методами, о которых она знает. И если даже мы унаследуем класс С от А и В, то метод processA, унаследованный из класса А, может работать только с внутренней переменной а, ибо о b он ничего не знает, равно как ничего он не знает и о c, и о методе processC. Точно так же и метод processB может работать только с переменной b. Т.е., по сути, унаследованные части оказываются изолированными. Класс С, безусловно, может с ними работать, но точно так же он может работать с этими частями, если они будут просто включены в его состав, а не унаследованы.

Однако тут есть еще одна неприятность, заключающаяся в перекрытии имен. Если бы методы processA и processB назывались одинаково, допустим, process, то какой эффект дало бы обращение к методу process класса С? Какой из двух методов был бы вызван? Разумеется, в С++ есть средства управления в этой ситуации, однако стройности языку это не добавляет.

Итак, преимуществ наследование реализации не дает, а недостатки есть. По этой причине это наследования реализации в Java отказались. Однако, разработчикам оставили такой вариант множественного наследования, как наследование от интерфейса. В терминах Java - реализация интерфейса.

Что представляет собой интерфейс? Набор методов. (Определение в интерфейсах констант мы сейчас не рассматриваем, подробнее об этом тут.) А что есть метод? А метод, по своей сути, определяет поведение объекта. Не случайно в названии практически каждого метода содержится действие - getXXX, drawXXX, countXXX, и т.д. А поскольку интерфейс - это совокупность методов, то интерфейс представляет собой, фактически, определитель поведения .

Другой вариант применения интерфейса - определитель роли объекта. Наблюдатель, Слушатель и т.п. В этом случае метод фактически является воплощением реакции на какое-то внешнее событие. Т.е., опять-таки, поведением.

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

Вернемся к ошибкам при наследовании. Мой опыт разработки различных систем показывает, что имея наследование от интерфейсов, можно реализовать любую систему, при этом не используя множественного наследования реализации. И потому, когда я встречаюсь с сетованиями на отсутствие множественного наследования в том виде, в котором оно есть в С++, для меня это верный признак неправильного дизайна.

2. Реализация типа

В предыдущем примере мы видели, что реализация передается через объект. Следовательно, в объекте упакована вся необходимая информация по реализации интерфейса. Если поведение определяется интерфейсом, а реализация упакована в объекте, то зачем нужен класс? - Классы нужны для наследования реализации и повторного использования кода. Если повторное использование не требуется, то и класс не нужен.