Реку́рсия — процесс повторения элементов самоподобным образом. Например, если два зеркала установить друг напротив друга, то возникающие в них вложенные отражения суть одна из форм бесконечной рекурсии.Термин «рекурсия» используется в различных специальных областях знаний — от лингвистики до логики, но наиболее широкое применение находит в математике и информатике. В математике и информатике рекурсия имеет отношение к методу определения функций: рекурсивно заданная функция в своём определении содержит себя, в частности, рекурсивной является функция, заданная рекуррентной формулой. Таким образом, можно одним выражением дать бесконечный набор способов вычисления функции, определить множество объектов через самого себя с использованием ранее заданных частных определений.
В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция вызывает функцию , а функция — функцию . Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
Преимущество рекурсивного определения объекта заключается в том, что такое конечное определение теоретически способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.
Реализация рекурсивных вызовов функций в практически применяемых языках и средах программирования, как правило, опирается на механизм стека вызовов — адрес возврата и локальные переменные функции записываются в стек, благодаря чему каждый следующий рекурсивный вызов этой функции пользуется своим набором локальных переменных и за счёт этого работает корректно. Оборотной стороной этого довольно простого по структуре механизма является то, что на каждый рекурсивный вызов требуется некоторое количество оперативной памяти
компьютера, и при чрезмерно большой глубине рекурсии может наступить переполнение стека вызовов. Вследствие этого, обычно рекомендуется избегать рекурсивных программ, которые приводят (или в некоторых условиях могут приводить) к слишком большой глубине рекурсии.
Имеется специальный тип рекурсии, называемый «хвостовой рекурсией». Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного или исполняемого), автоматически преобразуют хвостовую рекурсию к итерации, благодаря чему обеспечивается выполнение алгоритмов с хвостовой рекурсией в ограниченном объёме памяти. Такие рекурсивные вычисления, даже если они формально бесконечны (например, когда с помощью рекурсии организуется работа командного интерпретатора, принимающего команды пользователя), никогда не приводят к исчерпанию памяти. Однако, далеко не всегда стандарты языков программирования чётко определяют, каким именно условиям должна удовлетворять рекурсивная функция, чтобы транслятор гарантированно преобразовал её в итерацию. Одно из редких исключений — язык Scheme (диалект языка Lisp), описание которого содержит все необходимые сведения.
Любую рекурсивную функцию можно заменить циклом и стеком.
12 вопрос Массивы в языке Паскаль.
Поговорим о массивах в Паскале. Массив представляет собой последовательность элементов одного типа. Каждый массив характеризуется следующими особенностями:
каждый компонент, входящий в массив, можно обозначить явно и к нему устанавливается прямой доступ,
кол-во компонент, входящих в массив, может быть определено при его описании и в последующем не изменяется.
Чтобы обозначить компонент массива, используют имя переменной (переменной-массива), а также индексы, которые указывают необходимый элемент. Индекс может иметь только порядковый тип (за исключением longint). Часто используют интервальный тип (отрезок, диапазон). Приведем описание типа массива:
имя типа - правильный идентификатор;
список индексов - совокупность одного, либо нескольких индексных типов, которые отделяются друг от друга запятыми;
тип - всякий тип данных.
При работе с программой в Паскале массивы можно как вводить, так и выводить, лишь по одному элементу.
Одномерным массивом называется фиксированное число элементов одинакового типа.
Вот пример программы на одномерный массив: ввод и вывод.
Определение переменной в качестве массива возможно при ее описании без первоначального описания типа используемого массива:
В случае, когда массивы a и b описываются следующим образом:
то у переменных a и b будет разный тип. Чтобы обеспечить совместимость типов необходимо описать переменные через первоначальное описание типа. Если массивы имеют идентичные типы, то в исходном коде программы один массив можно присвоить другому. В соответствии с этим значения переменных одного массива присваиваются значениям элементов другого массива. Для массивов в Паскале не определены операции отношения. Сравнение двух массивов возможно только по каждому элементу.
Многомерные массивы - массивы, каждым элементом которых являются массивы.
Представим примеры описания двумерных массивов.
Пример 1.
Пример 2.
Глубина вложенности массивов представляется произвольной, вследствие этого размерность массива (число элементов, входящих в состав списка индексных типов) не ограничена, но не может превышать 65520 байт.
При работе с многомерными массивами мы организуем вложенные циклы. Например, для заполнения двумерного массива (матрицы) случайными числами пользуются следующими командами:
Чтобы красиво вывести на экран двумерный массив, используйте конструкцию вида: