В чем разница между рекурсией и итерацией?

Рекурсия vs Итерация

Рекурсия и итерация — это два фундаментальных подхода к повторению операций в программировании. Оба решают похожие задачи, но работают совершенно по-разному.

Рекурсия

Что это: Функция вызывает сама себя с другими параметрами, пока не достигнет базового случая (условия выхода).

Пример: факториал

# Рекурсивное решение
def factorial_recursive(n):
    # Базовый случай (условие выхода)
    if n <= 1:
        return 1
    # Рекурсивный случай
    return n * factorial_recursive(n - 1)

print(factorial_recursive(5))  # 120
# 5! = 5 * 4! = 5 * 4 * 3 * 2 * 1 = 120

Как работает:

factorial_recursive(5)
    ↓
5 * factorial_recursive(4)
    ↓
5 * 4 * factorial_recursive(3)
    ↓
5 * 4 * 3 * factorial_recursive(2)
    ↓
5 * 4 * 3 * 2 * factorial_recursive(1)
    ↓
5 * 4 * 3 * 2 * 1  (базовый случай)
    ↓
Result: 120

Stack (стек вызовов):

Call Stack:
[factorial_recursive(1)] → return 1
[factorial_recursive(2)] → return 2*1 = 2
[factorial_recursive(3)] → return 3*2 = 6
[factorial_recursive(4)] → return 4*6 = 24
[factorial_recursive(5)] → return 5*24 = 120

Итерация

Что это: Повторение блока кода (цикл) пока выполняется условие.

Пример: факториал с итерацией

# Итеративное решение
def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

print(factorial_iterative(5))  # 120
# 1 * 1 * 2 * 3 * 4 * 5 = 120

Как работает:

result = 1
    ↓
i = 1: result = 1 * 1 = 1
    ↓
i = 2: result = 1 * 2 = 2
    ↓
i = 3: result = 2 * 3 = 6
    ↓
i = 4: result = 6 * 4 = 24
    ↓
i = 5: result = 24 * 5 = 120
    ↓
Result: 120

Memory (Память):

Stack: [factorial_iterative, result=120]
Heap: [minimal data]

Сравнение

Примеры для разных задач

1. Факториал

# ❌ Рекурсия — медленнее, рискованнее
def fact_rec(n):
    return 1 if n <= 1 else n * fact_rec(n-1)

# ✅ Итерация — быстрее, безопаснее
def fact_iter(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

2. Поиск в бинарном дереве

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# ✅ Рекурсия — элегантна для деревьев
def search_recursive(node, target):
    if node is None:
        return False
    if node.val == target:
        return True
    return search_recursive(node.left, target) or search_recursive(node.right, target)

# ⚠️ Итерация — более громоздка (нужна очередь/стек)
def search_iterative(root, target):
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node is None:
            continue
        if node.val == target:
            return True
        queue.append(node.left)
        queue.append(node.right)
    return False

3. Сумма элементов списка

# ❌ Рекурсия
def sum_recursive(lst):
    if not lst:
        return 0
    return lst[0] + sum_recursive(lst[1:])

# ✅ Итерация
def sum_iterative(lst):
    total = 0
    for num in lst:
        total += num
    return total

# ✅ Pythonic (map + sum)
def sum_pythonic(lst):
    return sum(lst)

Проблемы с рекурсией

1. Stack Overflow

# Это вызовет RecursionError при n > ~1000
def bad_recursion(n):
    if n <= 0:
        return 1
    return bad_recursion(n - 1)

bad_recursion(10000)  # RecursionError: maximum recursion depth exceeded

Решение:

# Увеличить лимит (не рекомендуется для production)
import sys
sys.setrecursionlimit(50000)

# Или использовать итерацию
def good_iteration(n):
    result = 0
    for i in range(n):
        result += i
    return result

2. Performance overhead

import time

# Рекурсия
def fib_recursive(n):
    if n <= 1:
        return n
    return fib_recursive(n-1) + fib_recursive(n-2)

# Итерация
def fib_iterative(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# Benchmark
start = time.time()
print(fib_recursive(35))  # ~3 секунды
print(f"Рекурсия: {time.time() - start:.2f}s")

start = time.time()
print(fib_iterative(35))  # ~0.0001 секунды
print(f"Итерация: {time.time() - start:.2f}s")

# Итерация в 30000 раз быстрее!

Оптимизация рекурсии

1. Memoization (кэширование результатов)

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memoized(n):
    if n <= 1:
        return n
    return fib_memoized(n-1) + fib_memoized(n-2)

# Теперь рекурсия работает быстро
print(fib_memoized(100))  # Мгновенно

2. Tail Recursion (хвостовая рекурсия)

Python не оптимизирует хвостовую рекурсию, но в других языках это помогает:

# Хвостовая рекурсия (последний вызов — рекурсивный)
def factorial_tail(n, acc=1):
    if n <= 1:
        return acc
    return factorial_tail(n - 1, acc * n)

Когда использовать что

Используй РЕКУРСИЮ когда:

• Работаешь с древовидными структурами (файловая система, DOM)
• Граф или связный список
• Разделяй и властвуй алгоритмы (сортировка слиянием, quicksort)
• Глубина относительно мала (< 100)

Используй ИТЕРАЦИЮ когда:

• Простой перебор элементов массива
• Работаешь с линейными структурами
• Нужна максимальная производительность
• Глубина неизвестна или может быть велика

Выводы

• Рекурсия — элегантна и понятна, но медленнее и опаснее
• Итерация — практична и эффективна, стандартный выбор
• Оптимизация: memoization для рекурсии, если она не авoidible
• Best practice: Используй итерацию по умолчанию, рекурсию для специальных случаев