Умеешь ли работать с рекурсией в Python

# Рекурсия в Python

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

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

Каждая рекурсивная функция должна иметь:

1. Базовый случай (условие выхода) — когда функция останавливается
2. Рекурсивный случай — когда функция вызывает саму себя

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

# Факториал: 5! = 5 * 4 * 3 * 2 * 1 = 120

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

print(factorial(5))  # 120

Пример: сумма элементов списка

def sum_list(arr):
    # Базовый случай: пустой список
    if len(arr) == 0:
        return 0
    # Рекурсивный случай: первый элемент + сумма остальных
    return arr[0] + sum_list(arr[1:])

print(sum_list([1, 2, 3, 4, 5]))  # 15

Пример: поиск в дереве

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

def find_value_in_tree(node, target):
    # Базовый случай: дошли до листа
    if node is None:
        return False
    
    # Нашли значение
    if node.val == target:
        return True
    
    # Рекурсивный поиск в левом и правом поддереве
    return find_value_in_tree(node.left, target) or find_value_in_tree(node.right, target)

Проблемы рекурсии и их решения

1. Переполнение стека (Stack Overflow)

Python имеет лимит на глубину рекурсии (обычно 1000):

import sys

# Проверить текущий лимит
print(sys.getrecursionlimit())  # 1000

# Увеличить лимит (с осторожностью!)
sys.setrecursionlimit(10000)

# Пример проблемы: глубокая рекурсия
def count_down(n):
    if n == 0:
        return
    count_down(n - 1)  # может вызвать RecursionError при большом n

2. Оптимизация: мемоизация

Если функция многократно вызывается с одинаковыми аргументами, кешируй результаты:

from functools import lru_cache

# Без оптимизации: O(2^n) временная сложность
def fib_slow(n):
    if n <= 1:
        return n
    return fib_slow(n - 1) + fib_slow(n - 2)

# С мемоизацией: O(n) временная сложность
@lru_cache(maxsize=None)
def fib_fast(n):
    if n <= 1:
        return n
    return fib_fast(n - 1) + fib_fast(n - 2)

print(fib_fast(35))  # быстро: ~0.00001 сек вместо нескольких секунд

Пример: рекурсивное обхождение директорий

import os

def get_all_files(path, depth=0):
    indent = "  " * depth
    
    try:
        items = os.listdir(path)
    except PermissionError:
        return
    
    for item in items:
        item_path = os.path.join(path, item)
        
        if os.path.isfile(item_path):
            print(f"{indent}📄 {item}")
        elif os.path.isdir(item_path):
            print(f"{indent}📁 {item}/")
            # рекурсивно обходим подпапку
            get_all_files(item_path, depth + 1)

# Использование
get_all_files("/home/user/projects")

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

# Рекурсивное решение (элегантно, но медленнее)
def sum_recursive(arr):
    if len(arr) == 0:
        return 0
    return arr[0] + sum_recursive(arr[1:])

# Итеративное решение (быстрее, меньше памяти)
def sum_iterative(arr):
    total = 0
    for num in arr:
        total += num
    return total

# Или через встроенную функцию (оптимально)
def sum_builtin(arr):
    return sum(arr)

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

✅ Хорошо для:

• Деревья и графы (поиск, обход)
• Разделяй и властвуй (merge sort, quick sort)
• Задачи с естественной рекурсивной структурой
• Симметричные проблемы (скобки, парсинг)

❌ Избегай:

• Простых итеративных задач
• Когда нужна максимальная производительность
• На глубоко вложенных структурах (используй итерацию)

Рекурсия — мощный инструмент, который делает код элегантнее, если использовать её правильно.