Рекурсивные алгоритмы

2.1 Обход дерева файлов

Давай рассмотрим рекурсивный алгоритм для обхода дерева файлов. Алгоритм будет обходить каталог и все его подкаталоги, выводя список всех файлов и папок.

import os

def list_files_recursive(directory, indent=0):
    # Получаем список всех файлов и папок в текущем каталоге
    items = os.listdir(directory)
                
    for item in items:
        # Создаём полный путь к файлу или папке
        path = os.path.join(directory, item)
                    
        # Выводим с отступом для лучшего восприятия структуры
        print(' ' * indent + item)
                    
        # Если это папка, рекурсивно обходим её содержимое
        if os.path.isdir(path):
            list_files_recursive(path, indent + 4)
            
# Пример использования
root_directory = '/path/to/root/directory'
list_files_recursive(root_directory)

Как это работает?

1. Функция list_files_recursive(directory, indent=0):
   • directory — текущий каталог, содержимое которого мы хотим вывести.
   • indent — текущий уровень отступа, чтобы показать вложенность файлов и папок.
2. Получаем список всех файлов и папок в текущем каталоге с помощью os.listdir(directory).
3. Проходимся по каждому элементу в списке items.
4. Создаём полный путь к элементу с помощью os.path.join(directory, item).
5. Выводим имя элемента с отступом, который увеличивается на 4 пробела для каждого уровня вложенности.
6. Проверяем, является ли элемент папкой с помощью os.path.isdir(path). Если да, рекурсивно вызываем list_files_recursive(path, indent + 4) для обхода её содержимого.

Пример вывода:

Допустим, у нас есть следующая структура каталогов:

root_directory/
    file1.txt
    dir1/
        file2.txt
        file3.txt
        dir2/
            file4.txt
    file5.txt

При выполнении функции list_files_recursive(root_directory) мы получим следующий вывод:

file1.txt
dir1
    file2.txt
    file3.txt
    dir2
        file4.txt
file5.txt

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

2.2 Ханойские башни

Задача «Ханойские башни»

Ханойские башни — это классическая рекурсивная задача, которая включает перемещение дисков с одного стержня на другой с помощью вспомогательного стержня.

Правила:

1. Можно перемещать только один диск за раз.
2. Диск можно поместить только на пустой стержень или на диск большего размера.
3. Нужно переместить все диски с одного стержня на другой, используя вспомогательный стержень.

Вот рекурсивный алгоритм для решения этой задачи:

Алгоритм Ханойских башен решает задачу следующим образом:

1. Переместить n - 1 дисков с начального стержня на вспомогательный, используя целевой стержень.
2. Переместить оставшийся диск с начального стержня на целевой.
3. Переместить n - 1 дисков с вспомогательного стержня на целевой, используя начальный стержень.

Пример на Python

def hanoi_tower(n, source, target, auxiliary):
    if n == 1:
        print(f"Переместить диск 1 с {source} на {target}")
        return
    hanoi_tower(n - 1, source, auxiliary, target)
    print(f"Переместить диск {n} с {source} на {target}")
    hanoi_tower(n - 1, auxiliary, target, source)
        
# Пример использования:
n = 3  # Количество дисков
hanoi_tower(n, 'A', 'C', 'B')
        

Как это работает?

Базовый случай:

Если есть только один диск (n == 1), то его можно просто переместить с начального стержня на целевой.

if n == 1:
    print(f"Переместить диск 1 с {source} на {target}")
    return

Рекурсивный случай:

Шаг 1. Переместить n - 1 диск с начального стержня на вспомогательный, используя целевой стержень.

hanoi_tower(n - 1, source, auxiliary, target)

Шаг 2. Переместить диск n с начального стержня на целевой.

print(f"Переместить диск {n} с {source} на {target}")

Шаг 3. Переместить n - 1 диск с вспомогательного стержня на целевой, используя начальный стержень.

hanoi_tower(n - 1, auxiliary, target, source)

Пример вывода:

Для трёх дисков (n = 3) на стержнях A, B и C, программа выведет:

Переместить диск 1 с A на C
Переместить диск 2 с A на B
Переместить диск 1 с C на B
Переместить диск 3 с A на C
Переместить диск 1 с B на A
Переместить диск 2 с B на C
Переместить диск 1 с A на C

2.3 Снежинка Коха

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

Алгоритм для рисования снежинки Коха

Кривая Коха строится следующим образом:

• Начинаем с прямой линии.
• Разбиваем каждый отрезок на три части и заменяем центральную часть небольшой кривой, напоминающей «уголок».
• Повторяем этот процесс рекурсивно для каждого отрезка.

Пошаговая инструкция

• Начало: Нарисуйте начальный отрезок.
• Разделение: Разделите каждый отрезок на три части.
• Замените центральную часть: На центральной части нарисуйте «уголок», состоящий из двух линий, образующих угол 60 градусов.
• Повторите процесс: Продолжайте этот процесс для каждого отрезка.

Пример на Python с использованием библиотеки Turtle

import turtle

def draw_koch_curve(t, length, depth):
    if depth == 0:
        t.forward(length)
    else:
        length /= 3.0
        draw_koch_curve(t, length, depth - 1)
        t.left(60)
        draw_koch_curve(t, length, depth - 1)
        t.right(120)
        draw_koch_curve(t, length, depth - 1)
        t.left(60)
        draw_koch_curve(t, length, depth - 1)
            
def draw_snowflake(t, length, depth):
    for _ in range(3):
        draw_koch_curve(t, length, depth)
        t.right(120)
            
# Настройка экрана
screen = turtle.Screen()
screen.bgcolor("sky blue")
            
# Настройка черепашки
t = turtle.Turtle()
t.speed(0)
t.color("white")
            
# Рисуем снежинку
t.penup()
t.goto(-100, 50)
t.pendown()
draw_snowflake(t, 300, 4)
            
# Завершение рисования
turtle.done()
            

Как это работает?

1. Функция draw_koch_curve(t, length, depth):

• t: черепашка, которая рисует.
• length: длина отрезка.
• depth: глубина рекурсии, определяющая уровень детализации.

2. Базовый случай:

Если depth равен 0, черепашка рисует прямой отрезок.

if depth == 0:
    t.forward(length)
        

3. Рекурсивный случай:

Разделите отрезок на три части, и примените draw_koch_curve рекурсивно к каждой части, добавляя повороты.

length /= 3.0
draw_koch_curve(t, length, depth - 1)
t.left(60)
draw_koch_curve(t, length, depth - 1)
t.right(120)
draw_koch_curve(t, length, depth - 1)
t.left(60)
draw_koch_curve(t, length, depth - 1)

4. Функция draw_snowflake(t, length, depth):

Рисует три кривые Коха, соединённые в одну снежинку.

for _ in range(3):
    draw_koch_curve(t, length, depth)
    t.right(120)

Как запустить код?

• Убедитесь, что у вас установлена библиотека Turtle (pip install PythonTurtle).
• Скопируйте и вставьте код в файл .py и запустите его. Вы увидите рисование снежинки на экране.

Этот алгоритм позволяет визуализировать фрактальную структуру снежинки с использованием простых принципов рекурсии и геометрических построений.