4. Рекурсия

Объект называется рекурсивным, если он содержит сам себя или определен с помощью самого себя [2].

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

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

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

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

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

Пример. Реализовать вычисление факториала n! рекурсивно. Решение оформим программой на языке С++.

// Вычисление факториала n! рекурсивно

#include "stdafx.h"

#include <iostream>

using namespace std;

#include <conio.h>

int fact(int i);

int _tmain(int argc, _TCHAR* argv[])

{

int n;

cout<<"Enter n = ";

cin>>n;

cout<<" \n n! = "<<fact(n)<<"\n";

getch();

return 0;

}

int fact(int i)

{

if(i<=1) return 1;

return i*fact(i-1);

}

2. Информационные структуры

   1. Последовательное и связанное распределение данных

Последовательное распределение

С вычислительной точки зрения простейшим представлением [3] конечной последовательности является список ее членов, расположенных по порядку в последовательных ячейках памяти.

 d 

Ячейка памяти	S1	S2	S3	…	Sn-1	Sn
Адреса ячеек памяти	l1	l2	l3		ln-1	ln

l₂ = l₁ + d

l₃ = l₁ + 2d

…

l_n = l₁ + (n-1) d

Таким образом, представляется последовательное распределение данных S₁, S₂,…, S_n, для каждого элемента которой требуется объем памяти d, l_i — адрес ячейки.

Такое представление имеет ряд преимуществ. Во-первых, оно легко осуществимо и требует небольших расходов памяти. Во-вторых, существует простое соотношение между номером элемента i и адресом ячейки, в которой хранится S_i: l_i = l₁ + (i-1) d. Это соотношение позволяет организовать прямой доступ к любому элементу последовательности. В-третьих, оно имеет широкий диапазон и включает в себя представление многомерных массивов.

Последовательное распределение имеет значительный недостаток. Оно становится неудобным, если требуется изменить последовательность путем включения новых и исключения имеющихся там элементов. Включение между S_i и S_i+1 нового элемента требует сдвига S_i+1, … S_n вправо на одну позицию, а исключение соответственно — сдвиг влево.

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

Связанное распределение

Неудобство включения и исключения элементов при последовательном распределении происходит из-за того, что порядок следования элементов задается неявно требованием, чтобы смежные элементы последовательности находились в смежных ячейках памяти. Если это требование опустить, то можно выполнять операции включения и исключения без передвижения элементов последовательности. Конечно, необходимо сохранять информацию о способе упорядочения элементов, но можно это делать явным образом. В частности, при связанном распределении данных каждому S_i поставлен в соответствие указатель Р_i, отмечающий ячейку, в которой записаны S_i+1 и P_i+1 (т.е. переход на следующую ячейку последовательности). Существует также указатель P₀, который указывает на начальную ячейку последовательности, т.е. на ячейку с содержимым S₁ и P₁.

(INFO) (LINK)

P0=l1	S1	P1=l2		S2	P2=l3	…	Sn-1	Pn-1=ln		Sn	Pn=
	l1			l2			l n-1			l n

Рис. 2.1. Представление последовательности в виде связанного списка.

Каждый элемент списка состоит из поля INFO (содержащего элемент последовательности) и поля LINK (содержащего адрес следующего элемента)

Здесь каждый узел состоит из двух полей. Под узлом понимается одно или несколько последовательных слов в памяти машины, выступающих как единое целое.  — пустой или нулевой указатель. Рассмотрим более употребляемый способ задания списка.

P0	S1			S2		…	Sn-1			Sn

Рис. 2.2. Способ задания списка

Связанное представление данных облегчает операции включения и исключения элемента, если ячейка S_i известна. Для этого лишь необходимо, изменить значение некоторых указателей. Например, чтобы исключить элемент S₂ из последовательности, изображенной на рис. 2.2, необходимо положить LINK(l₁)=LINK(l₂). После этой операции элемента S₂ в последовательности больше не будет.

P0	S1			S2			S3		…

Рис. 2.3. Исключение элемента из связанного списка

Чтобы в последовательность (рис. 2.2) включить новый элемент S₅ после S₁, необходимо воспроизвести новый элемент в некоторой ячейке l₅ с INFO(l₅) = S₅ и LINK(l₅) = LINK(l₁) и присвоить LINK(l₁) l₅.

P0	S1			S2			S3		…

S5
l5

Рис. 2.4. Включение элемента в связанный список

Также легко осуществляется сцепление последовательностей и разбиение последовательности на части.

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

С помощью связанного распределения достигается большая гибкость, но идет потеря скорости обращения к данным. При последовательном представлении фиксированное соотношение между i и ячейкой S_i позволяет, в частности, иметь быстрый и прямой доступ к любому элементу последовательности. В связанном распределении такого соотношения не существует, и доступ ко всем элементам последовательности, кроме первого, не является прямым и эффективным. Кроме того, при связанном представлении приходится тратить память на P_i.

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

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

Разновидности связанных списков

Если P_n указывает на S₁, то такая форма списка дает возможность достигнуть любой элемент списка (хотя и не прямо) из любого другого элемента последовательности.

P₀

S1

S2

…

Sn-1

Sn

Рис. 2.5. Циклический список

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

Большая гибкость при работе со списками достигается, если использовать дважды связанный список, когда каждый элемент S_i последовательности вместо одного имеет 2 связанных с ним указателя, они указывают на элементы S_i-1 и S_i+1.

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

P₀



S1

S2

…

Sn-1

Sn



Рис. 2.6. Дважды связанный список