10 класс Информатика ГДЗ учебник Поляков 2 часть Параграф 61 Рекурсия
Стр.202-203.
1. Рекурсия — это метод программирования, при котором функция вызывает саму себя для решения подзадач, составляющих основную задачу. Примеры рекурсии включают вычисление факториала числа и решение задачи «Ханойские башни».
2. Любое рекурсивное определение состоит из двух частей: базового случая и рекурсивного шага. Базовый случай предоставляет точку остановки для рекурсии, а рекурсивный шаг позволяет функции вызывать саму себя, решая подзадачи.
3. Задача «Ханойские башни» заключается в перемещении набора дисков различного диаметра с одного стержня на другой, используя третий стержень в качестве вспомогательного, при этом на больший диск нельзя класть меньший. Алгоритм без рекурсии можно реализовать с помощью стека или итеративного метода.
4. Обе процедуры можно назвать рекурсивными, поскольку процедура В вызывает саму себя напрямую, а также косвенно через процедуру А.
5. Рекурсия никогда не остановится, если не будет достигнут базовый случай, который завершает выполнение функции. В рассмотренных задачах базовые случаи определены, что гарантирует остановку рекурсии.
6. Стек — это структура данных, используемая для хранения информации о состоянии программы, такой как локальные переменные и адреса возврата. При выполнении рекурсивных вызовов в стек добавляются новые элементы, а при возврате из функций они удаляются.
7. Переполнение стека может случиться, если количество рекурсивных вызовов слишком велико и стековая память исчерпывается. Это может произойти при глубокой рекурсии или при использовании большого количества локальных переменных.
8. Достоинства рекурсии включают простоту и наглядность кода при решении задач с вложенной структурой. Недостатки включают возможность переполнения стека и более медленное выполнение по сравнению с итеративными методами. Рекурсию следует использовать, когда задача естественно разбивается на подзадачи, а итеративные методы предпочтительны, когда необходимо избежать глубоких вызовов.
Проекты
а) Рекурсия в рекламе и в искусстве
Рекурсия используется в искусстве и рекламе для создания эффектов бесконечных повторений и фрактальных узоров. Примеры включают плакаты с повторяющимися изображениями и фрактальные рисунки в графическом дизайне.
б) Рекурсивныеалгоритмы без рекурсии
Рекурсивные алгоритмы могут быть переписаны в итеративной форме с использованием структур данных, таких как стек или очередь. Пример: итеративный алгоритм для вычисления факториала числа.
в) Программа для построения фракталов
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | import turtle def draw_sierpinski(length, depth): if depth == 0: for _ in range(3): turtle.forward(length) turtle.left(120) else: draw_sierpinski(length / 2, depth - 1) turtle.forward(length / 2) draw_sierpinski(length / 2, depth - 1) turtle.backward(length / 2) turtle.left(60) turtle.forward(length / 2) turtle.right(60) draw_sierpinski(length / 2, depth - 1) turtle.left(60) turtle.backward(length / 2) turtle.right(60) turtle.speed(0) draw_sierpinski(200, 4) turtle.done() |
г) Рекурсивный перебор вариантов
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | def permute(s, answer): if len(s) == 0: print(answer) return for i in range(len(s)): ch = s[i] left_substr = s[0:i] right_substr = s[i + 1:] rest = left_substr + right_substr permute(rest, answer + ch) s = input("Введите строку: ") answer = "" permute(s, answer) |
| 59 | 60 | 61 | 62 | 63 |