29 Вопрос Рекурсия в программировании [править]Функции
Блок схема рекурсивного алгоритма решения Ханойской башни.
В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция вызывает функцию , а функция — функцию . Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
Преимущество рекурсивного определения объекта заключается в том, что такое конечное определение теоретически способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.
Реализация рекурсивных вызовов функций в практически применяемых языках и средах программирования, как правило, опирается на механизм стека вызовов — адрес возврата и локальные переменные функции записываются в стек, благодаря чему каждый следующий рекурсивный вызов этой функции пользуется своим набором локальных переменных и за счёт этого работает корректно. Оборотной стороной этого довольно простого по структуре механизма является то, что на каждый рекурсивный вызов требуется некоторое количество оперативной памяти компьютера, и при чрезмерно большой глубине рекурсии может наступить переполнение стека вызовов. Вследствие этого, обычно рекомендуется избегать рекурсивных программ, которые приводят (или в некоторых условиях могут приводить) к слишком большой глубине рекурсии.
Имеется специальный тип рекурсии, называемый «хвостовой рекурсией». Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного или исполняемого), автоматически преобразуют хвостовую рекурсию к итерации, благодаря чему обеспечивается выполнение алгоритмов с хвостовой рекурсией в ограниченном объёме памяти. Такие рекурсивные вычисления, даже если они формально бесконечны (например, когда с помощью рекурсии организуется работа командного интерпретатора, принимающего команды пользователя), никогда не приводят к исчерпанию памяти. Однако, далеко не всегда стандарты языков программирования чётко определяют, каким именно условиям должна удовлетворять рекурсивная функция, чтобы транслятор гарантированно преобразовал её в итерацию. Одно из редких исключений — язык Scheme (диалект языка Lisp), описание которого содержит все необходимые сведения.
Любую рекурсивную функцию можно заменить циклом и стеком.
- 3 Вопрос.
- Языки программирования низкого уровня
- Преимущества
- Недостатки
- Языки программирования высокого уровня
- 4 Вопрос.
- 5 Вопрос.
- Синтаксис и языковые конструкции
- Семантика языков программирования
- 6 Вопрос.
- 12 Вопрос. Символьные типы
- Логический тип
- 14 Вопрос
- 20 Вопрос
- 21 Вопрос
- 22 Вопрос
- 23 Вопрос
- Присваивание (ввод/вывод);
- Сравнение
- Конкатенацию.
- 25 Вопрос
- 26 Вопрос
- 27 Вопрос.
- 28 Вопрос
- 29 Вопрос Рекурсия в программировании [править]Функции
- 31 Вопрос
- Краткое описание алгоритма
- 32 Вопрос
- 33 Вопрос. Операции с файлом
- [Править]Операции, связанные с открытием файла
- 34 Вопрос. Стандартные процедуры и функции для текстовых и типизированных файлов