1. Что такое рекурсия? Приведите примеры.
Рекурсия – это метод решения задачи, при котором функция вызывает саму себя. Основная идея рекурсии заключается в том, чтобы разбить задачу на более мелкие подзадачи такого же типа, пока не будет достигнуто условие завершения. Примеры:
Вычисление факториала числа n (n!): n! = n * (n - 1)!, где 1! = 1. Числа Фибоначчи: F(n) = F(n - 1) + F(n - 2), где F(0) = 0 и F(1) = 1.
2. Как вы думаете, почему любое рекурсивное определение состоит из двух частей?
Базовый случай, который завершает рекурсию, предотвращая её бесконечный вызов. Например, в факториале базовый случай – это n = 1. Рекурсивный случай, который задаёт правило перехода для более сложного состояния задачи. Например, в факториале n! = n * (n - 1)!. Это разделение необходимо, чтобы задача могла быть решена конечным числом шагов и чтобы избежать бесконечной рекурсии.
3. Расскажите о задаче «Ханойские башни». Попытайтесь придумать или найти в дополнительных источниках алгоритм её решения, не использующий рекурсию.
Дано три стержня и n дисков, расположенных на первом стержне в порядке убывания размера. Требуется переместить все диски на третий стержень, соблюдая правила: Можно перемещать только один диск за раз. Нельзя класть больший диск на меньший. Нерекурсивный алгоритм:
Используется метод итеративного решения на основе двоичной записи чисел. Числа от 1 до 2^n - 1 представляют последовательность действий. Если номер шага нечётный, перемещается самый маленький диск в разрешённом направлении (по часовой стрелке или против, в зависимости от количества дисков). Если номер шага чётный, перемещается другой разрешённый диск. Повторять, пока все диски не окажутся на третьем стержне. Этот подход требует чёткого отслеживания последовательности действий, но полностью исключает рекурсию.
4. Процедура А вызывает процедуру Б, а процедура Б — процедуру А и сама себя. Какую из них можно назвать рекурсивной?
Рекурсивной можно назвать процедуру Б, поскольку она вызывает саму себя. Процедура А, которая вызывает только процедуру Б, не является рекурсивной, так как не имеет прямого самовызова.
5. В каком случае рекурсия никогда не остановится? Докажите, что в рассмотренных в параграфе задачах этого не случится.
Рекурсия никогда не остановится, если не предусмотрен базовый случай, который завершает выполнение функции. Без базового случая рекурсивные вызовы будут продолжаться бесконечно, что приведёт к переполнению стека.
В рассмотренных задачах, таких как вычисление факториала или чисел Фибоначчи, предусмотрены базовые случаи:
В факториале базовый случай: n = 1, где возвращается 1. В числах Фибоначчи базовые случаи: F(0) = 0 и F(1) = 1. Такое объяснение обеспечивает завершение рекурсии и делает алгоритмы корректными.
Теперь текст выглядит аккуратно и легко копируется.
6. Что такое стек? Как он используется при выполнении программ?
Стек — это структура данных, работающая по принципу LIFO (последним пришёл — первым вышел). Он представляет собой упорядоченную последовательность, где добавление (push) и удаление (pop) элементов происходит только с одного конца — вершины стека. При выполнении программ стек используется для хранения информации о вызовах функций:
Адрес возврата (место в коде, куда нужно вернуться после завершения функции). Локальные переменные функции. Параметры, переданные в функцию. Когда функция вызывается, информация записывается в стек. Когда выполнение функции завершается, данные удаляются из стека, и управление передаётся обратно в вызывающую функцию.
7. Почему при использовании рекурсии может случиться переполнение стека?
Рекурсивная функция вызывает себя слишком много раз, создавая большое количество стековых фреймов. Базовый случай отсутствует или не достигается, и рекурсия становится бесконечной. Каждый рекурсивный вызов создаёт новый фрейм в стеке, а размер стека ограничен системой. При превышении лимита программа аварийно завершает работу.
8. Назовите достоинства и недостатки рекурсии. Когда её следует использовать, а когда — нет?
Достоинства рекурсии: Простота и лаконичность кода для задач, которые естественно выражаются рекурсивно (например, обход дерева, задачи на деление). Удобство для решения задач, где требуется многократное разбиение проблемы на подзадачи. Недостатки рекурсии:
Более высокая затратность по памяти из-за создания стековых фреймов. Риск переполнения стека. Иногда менее производительна по сравнению с итеративными решениями. Рекурсию следует использовать:
Когда задача имеет естественное рекурсивное описание (например, обход дерева, алгоритмы "разделяй и властвуй"). Когда лаконичность и читаемость кода важнее производительности. Рекурсию лучше не использовать:
В задачах, где глубина рекурсии велика, а стек может переполниться. Когда важно оптимизировать использование памяти или повысить производительность. В таких случаях предпочтительнее применять итеративные алгоритмы.