'A' in ['A', 'B'] даст TRUE,
2 in [1, 3, 6] даст FALSE.
Рекурсия — метод определения класса объектов или методов предварительным заданием одного или нескольких (обычно простых) его базовых случаев или методов, а затем заданием на их основе правила построения определяемого класса.
Другими словами, рекурсия — частичное определение объекта через себя, определение объекта с использованием ранее определённых. Рекурсия используется, когда можно выделить самоподобие задачи.
В программировании рекурсия — вызов функции или процедуры из неё же самой (обычно с другими значениями входных параметров), непосредственно или через другие функции (например, функция А вызывает функцию B, а функция B — функцию A). Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
Мощь рекурсивного определения объекта в том, что такое конечное определение способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.
Имеется специальный тип рекурсии, называемый «хвостовой рекурсией». Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного и/или исполняемого), выполняют хвостовую рекурсию в ограниченном объёме памяти при помощи итераций.
Следует избегать избыточной глубины рекурсии, так как это может вызвать переполнение стека вызовов.
Если процедура или функция в ходе выполнения вызывает саму себя, то мы имеем дело с рекурсией. Такой вызов процедур или функций может возникнуть либо вследствие рекурсивного описания, либо вследствие рекурсивного обращения. Рекурсивное описание предполагает, что в исполняемой части блока процедуры или функции присутствует обращение к ней самой. Примером рекурсивного описания может служить функция вычисления факториала:
Function Factorial (N: Integer): Integer;
Begin
if N = 1 Then Factorial:= 1
Else Factorial:= N*Factorial(N -1)
End;
Здесь Factorial(N) определяется через значение Factorial(N-1), которое определяется через Factorial(N-2), и т.д. до сведения к значению Factorial(0), которое определено явно и равно 1. Любое рекурсивное описание должно содержать явное определение для некоторых значений аргумента (или аргументов), так как иначе процесс сведения оказался бы бесконечным. Таким образом при рекурсивном описании необходимо наличие базовой части описания, которая обеспечивала бы завершение рекурсивных вызовов функции (процедуры).Рекурсивное обращение можно рассмотреть на примере вычисления определенного двойного интеграла по формуле трапеций. Точность этого приближения тем выше, чем больше число участков разбиения n. Увеличивая число n, можно достигнуть заданной точности. Если, допустим, функция TRAP вычисляет интеграл по методу трапеций при заданном числе интервалов N и А, В - пределы интегрирования, а FN - функция вычисления подынтегрального выражения, вычисление двойного интеграла можно осуществить с помощью следующего рекурсивного обращения к функции TRAP: J:= TRAP (N1, A1, B1, TRAP (N2, A2, B2, FN));
Ниже приведена рекурсивная функция, предназначенная для вычисления наибольшего общего делителя двух целых чисел N1 и N2.
Пример.
Function HighFactor(N1,N2:lnteger):lnteger;
Var P: Integer;
Begin
lf N1 > N2 Then P:=HighFactor(N1,N2)
Else
If N2<=0 Then p:= N1 {нерекурсивное решение}
Else P:=HighFactor(N2,N1 Mod N2);
HighFactor:= P
End;
Для того чтобы выполнение рекурсивной программы завершалось, необходимо существование в наиболее простых случаях нерекурсивного решения. В противном случае не исключено зацикливание.
Некоторые алгоритмы гораздо проще описать, используя рекурсию, нежели итерацию. Это относится в первую очередь к алгоритмам, работающим с разного рода списковыми структурами.
Использование рекурсивных процедур и функций делает программу в целом более гибкой и наглядной, но не всегда эффективной, так как работает такая программа, как правило, медленнее и требуют больше памяти. Дело в том, что при каждом вызове рекурсивной процедуры или функции отводится память под локальные переменные.
При сравнении итерационных методов решения и методов, использующих рекурсию, часто эффективными оказываются первые. Таким образом, рекурсию следует применять только там, где нет очевидного итерационного решения. Уровень вложенности рекурсий может быть ограничен в конкретных реализациях языка.
Различают прямую и косвенную рекурсию. Функция HighFactor является характерным примером прямой рекурсии. Косвенная рекурсия возникает тогда, когда один блок вызывает второй, а второй, в свою очередь, первый.
Динамические структуры данных; списки: основные виды и способы реализации. Технологии программирования
Способы конструирования программ
Динамические структуры данных – сложные, организованные определенным образом данные, которые могут менять размер и/или свою структуру во время работы программы. Т
Типичными динамическими структурами являются массивы, стеки, очереди, списки, деревья. Универсальными способами организации таких структур является использование указателей.
Указатели – переменные, содержащие не сами данные, а адреса памяти.
Стек – линейная динамическая структура, у которой в каждый момент времени доступным является последний ее элемент. Стеки упорядочены, неоднородны (элементы стэка могут относиться к разным типам).
Previous – указатель на тип элемента stack
Массивы – последовательность упорядоченных, индексированных значений одного типа.
Количество элементов динамических массивов можно изменять во время работы.
| Stack Item | Queue Item | List Item |
| Data | Data | Data |
| Previous | Next | Pointes |
Описание динам. массива: TypeName = Array of BaseType
Очередь – линейная динамическая структура. Отличается от стэка тем, что при добавлении элемент помещается в конец очереди.
Список – линейная динамическая структура связанных элементов.
Для списка определены следующие операции:
Вставка элемента в список;
Удаление элемента из списка;
Перемещение элемента по списку;
Извлечение данных элемента списка;
Поиск элемента и сортировка (дополнительно).
Pointes – указатели для перемещения по списку.
Если каждый элемент имеет указатель на один соседний элемент, то список однонаправленный. Перемещение производится в одну сторону. Если на 2 элемента, то двунаправленный.
Списки представляют собой структуру последовательного доступа, так как в каждый момент времени доступен только текущий элемент. Для доступа к остальным необходимо последовательное перемещение по списку с помощью указателей на соседний элемент.
Для реализации двунаправленного списка элемент должен содержать данные data и указатели previous и next на предыдущий и последующий элемент соответственно. Перемещение по списку осуществляется простыми перемещениями указателя Current на предыдущий и последующий элемент.
В языках программирования (Pascal, C, др.) существует и другой способ выделения памяти под данные, который называется динамическим. В этом случае память под величины отводится во время выполнения программы. Такие величины будем называть динамическими. Раздел оперативной памяти, распределяемый статически, называется статической памятью; динамически распределяемый раздел памяти называется динамической памятью (динамически распределяемой памятью).
Использование динамических величин предоставляет программисту ряд дополнительных возможностей. Во-первых, подключение динамической памяти позволяет увеличить объем обрабатываемых данных. Во-вторых, если потребность в каких-то данных отпала до окончания программы, то занятую ими память можно освободить для другой информации. В-третьих, использование динамической памяти позволяет создавать структуры данных переменного размера.
Работа с динамическими величинами связана с использованием еще одного типа данных — ссылочного типа. Величины, имеющие ссылочный тип, называют указателями.
Указатель содержит адрес поля в динамической памяти, хранящего величину определенного типа. Сам указатель располагается в статической памяти.
Адрес величины — это номер первого байта поля памяти, в котором располагается величина. Размер поля однозначно определяется типом.
Далее будем более подробно обсуждать указатели и действия с ними в языке Pascal.
В версиях Турбо-Паскаля, работающих под операционной системой MS DOS, под данные одной программы выделяется 64 килобайта памяти (или, если быть точнее, 65520 байт). Это и есть статическая область памяти. При необходимости работать с большими массивами информации этого может оказаться мало. Размер динамической памяти — много больше (сотни килобайт). Поэтому использование динамической памяти позволяет существенно увеличить объем обрабатываемой информации.
Следует отчетливо понимать, что работа с динамическими данными замедляет выполнение программы, поскольку доступ к величине происходит в два шага: сначала ищется указатель, затем по нему — величина. Как это часто бывает, действует "закон сохранения неприятностей": выигрыш в памяти компенсируется проигрышем во времени.
Технология программирования - это совокупность методов и средств разработки (написания) программ и порядок применения этих методов и средств. Основные походы:
Операциональный подход. В эпоху ЭВМ 1 - го и 2-го поколений основным требованием к алгоритму была его узко понимаемая эффективность:
1) минимальные требования в отношении оперативной памяти компьютера - программа должна была использовать наименьшее возможное число ячеек оперативной памяти компьютера;