Зачем нужна рекурсия?

Рекурсия в программировании

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

Основной принцип

Каждый рекурсивный вызов работает с уменьшенной версией проблемы, пока не достигнется базовый случай (base case) — условие, при котором рекурсия прерывается.

# Структура рекурсивной функции
def recursive_function(data):
    # 1. Базовый случай (условие выхода)
    if is_base_case(data):
        return base_result
    
    # 2. Рекурсивный случай
    # Функция вызывает саму себя с упрощённым аргументом
    return process(data) + recursive_function(simplify(data))

Примеры использования рекурсии

1. Факториал

# Рекурсивное определение факториала
def factorial(n):
    # Базовый случай
    if n <= 1:
        return 1
    
    # Рекурсивный случай: n! = n * (n-1)!
    return n * factorial(n - 1)

print(factorial(5))  # 120 (5 * 4 * 3 * 2 * 1)

2. Поиск в иерархической структуре (дереве)

# Структура дерева файлов
class TreeNode:
    def __init__(self, name, children=None):
        self.name = name
        self.children = children or []

# Рекурсивный поиск в дереве
def find_in_tree(node, target):
    # Базовый случай: нашли или листья закончились
    if node.name == target:
        return node
    
    # Рекурсивный случай: ищем в дочерних узлах
    for child in node.children:
        result = find_in_tree(child, target)
        if result:
            return result
    
    return None

# Использование
root = TreeNode("root", [
    TreeNode("folder1", [
        TreeNode("file1.txt"),
        TreeNode("file2.txt")
    ]),
    TreeNode("folder2")
])

found = find_in_tree(root, "file1.txt")
print(found.name)  # file1.txt

3. Обход каталогов

import os

def list_all_files(path):
    # Базовый случай: если файл — вывести его
    if os.path.isfile(path):
        print(path)
        return
    
    # Рекурсивный случай: если папка — обойти содержимое
    if os.path.isdir(path):
        for item in os.listdir(path):
            item_path = os.path.join(path, item)
            list_all_files(item_path)  # Рекурсивный вызов

list_all_files("/home/user/documents")

4. Обход графа (поиск в глубину — DFS)

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    
    # Базовый случай: уже посетили
    if node in visited:
        return visited
    
    visited.add(node)
    print(f"Посетили узел: {node}")
    
    # Рекурсивный случай: посещаем соседей
    for neighbor in graph[node]:
        dfs(graph, neighbor, visited)
    
    return visited

# Граф в виде словаря
graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"]
}

dfs(graph, "A")
# Посетили узел: A
# Посетили узел: B
# Посетили узел: D
# Посетили узел: C

5. Разбор вложенных структур

def flatten_nested_list(nested_list):
    result = []
    
    for item in nested_list:
        # Базовый случай: если это не список
        if not isinstance(item, list):
            result.append(item)
        # Рекурсивный случай: если список — расплющиваем
        else:
            result.extend(flatten_nested_list(item))
    
    return result

data = [1, [2, 3, [4, 5]], 6, [7, [8, 9]]]
flattened = flatten_nested_list(data)
print(flattened)  # [1, 2, 3, 4, 5, 6, 7, 8, 9]

Проблемы рекурсии: Stack Overflow

Проблема: Слишком глубокая рекурсия

# Плохо: для больших n вызовет RecursionError
def sum_recursive(n):
    if n <= 0:
        return 0
    return n + sum_recursive(n - 1)

sum_recursive(100000)  # RecursionError: maximum recursion depth exceeded

Решение 1: Увеличить лимит рекурсии

import sys
sys.setrecursionlimit(1000000)  # Опасно! Может привести к краху
sum_recursive(100000)

Решение 2: Использовать итерацию (оптимальное)

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

print(sum_iterative(100000))  # Работает быстро и безопасно

Решение 3: Tail Recursion Optimization (TCO)

Python не оптимизирует хвостовую рекурсию автоматически, но можно использовать декоратор:

import sys

def tail_recursive(func):
    def wrapper(*args, **kwargs):
        result = func(*args, **kwargs)
        while callable(result):
            result = result()
        return result
    return wrapper

@tail_recursive
def sum_tail(n, acc=0):
    if n <= 0:
        return acc
    return lambda: sum_tail(n - 1, acc + n)

print(sum_tail(10000))  # Работает благодаря TCO

Мемоизация для оптимизации

Проблема: Дублирующиеся вычисления

# Неэффективно: fibonacci(5) вычисляет fibonacci(3) много раз
def fib_slow(n):
    if n <= 1:
        return n
    return fib_slow(n - 1) + fib_slow(n - 2)

fib_slow(40)  # Занимает минуты!

Решение: Кэширование результатов (мемоизация)

from functools import lru_cache

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

fib_fast(100)  # Мгновенно! Благодаря кэшированию

# Или вручную:
cache = {}

def fib_manual(n):
    if n in cache:
        return cache[n]
    
    if n <= 1:
        return n
    
    result = fib_manual(n - 1) + fib_manual(n - 2)
    cache[n] = result
    return result

Когда использовать рекурсию

✅ Используй рекурсию для:

# 1. Структур, естественно рекурсивных (деревья, графы)
class Node:
    def __init__(self, value, children=None):
        self.value = value
        self.children = children or []

def process_tree(node):
    print(node.value)
    for child in node.children:
        process_tree(child)  # Рекурсия идеальна тут

# 2. Разбора/компиляции кода (парсеры, компиляторы)
def parse_expression():
    left = parse_term()
    while current_token() == "+":
        consume("+")
        right = parse_term()
        left = BinaryOp(left, "+", right)
    return left

# 3. Задач с делением и властью (divide-and-conquer)
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)  # Рекурсия здесь естественна

❌ Избегай рекурсии для:

# 1. Простых циклов
# Плохо:
def sum_recursive(n, acc=0):
    if n == 0:
        return acc
    return sum_recursive(n - 1, acc + n)

# Хорошо:
def sum_iterative(n):
    return sum(range(1, n + 1))

# 2. Очень больших наборов данных
# Плохо: может привести к Stack Overflow
def process_huge_list_recursive(lst):
    if not lst:
        return
    process(lst[0])
    return process_huge_list_recursive(lst[1:])

# Хорошо:
def process_huge_list_iterative(lst):
    for item in lst:
        process(item)

Вывод

Рекурсия полезна для:

• Древовидных и графовых структур — естественное отражение структуры данных
• Алгоритмов "Разделяй и властвуй" (merge sort, quicksort, binary search)
• Разбора и компиляции (парсеры, компиляторы)
• Задач, где каждый подзадача — уменьшенная копия оригинала

Но помни:

• Рекурсия может быть неэффективной (повторные вычисления)
• Глубокая рекурсия приводит к Stack Overflow
• Часто итеративное решение быстрее
• Используй мемоизацию для оптимизации

Эмпирическое правило: если решение без рекурсии просто и понятно — используй итерацию. Если рекурсия делает код ясным и элегантным — используй её с мемоизацией.