Вопрос проверяет понимание двух способов организации повторяющихся вычислений: циклы и рекурсивные вызовы функций.
Итерация использует циклы (for, while), а рекурсия — вызов функции самой себя. Итерация обычно быстрее и безопаснее по памяти, поэтому она предпочтительна для больших объёмов данных. Рекурсия удобна для задач с естественной древовидной структурой: обход дерева, разбиение, поиск. Однако чрезмерная глубина рекурсии может привести к переполнению стека.
Определение:
Итерация — выполнение повторений через циклы.
Рекурсия — вызов функции самой себя до достижения базового случая.
Итерация работает через циклы:
for — перебор итератора;
while — выполнение до условия.
Преимущества:
Быстрая работа (нет накладных вызовов функций);
Нет ограничений глубины;
Легче отлаживать.
Python
total = 0
for i in range(5):
total += i
Рекурсия строится на двух частях:
базовый случай — условие остановки;
рекурсивный вызов — уменьшение задачи.
Пример вычисления факториала:
Python
def fact(n: int) -> int:
if n == 1:
return 1
return n * fact(n - 1)
Преимущества рекурсии:
Естественна для деревьев и графов;
Упрощает логику в задачах divide-and-conquer.
Недостатки:
Может достичь предела глубины рекурсии;
Медленнее из-за вызовов функций.
Итерация:
большие линейные данные;
задачи без вложенных структур;
оптимизация производительности.
Рекурсия:
обход дерева (DFS);
разбиение данных (quicksort);
математические задачи с естественными рекурсивными определениями.
Обход дерева:
Python
def dfs(node):
if not node:
return
for child in node.children:
dfs(child)
Этот код рекурсивный, но итеративная версия была бы сложнее и менее читаемой.
Итерация — оптимальна по производительности, рекурсия — оптимальна по выразительности на древовидных структурах. Выбор зависит от структуры задачи и ограничений по памяти.
