📦 Репозиторий занятия 46

Рекурсия vs цикл: обратный отсчёт

less_24__recursion/theory_01_recursion_countdown.py

Сравнивает итеративную реализацию обратного отсчёта (countdown_loop с while True и break) с рекурсивной (countdown_recursion). Показывает структуру рекурсии на простейшем примере: базовый случай (n <= 0, печать 'Done!') и рекурсивный случай (печать n, вызов самой себя с n-1). Обе функции при n=2 дают идентичный результат.

• countdown_loop(n) — while True с ручным break при n <= 0
• countdown_recursion(n) — базовый случай: n <= 0 печатает 'Done!'
• countdown_recursion(n) — рекурсивный случай: печать n, return countdown_recursion(n-1)
• countdown_loop(2) и countdown_recursion(2) — вызовы дают одинаковый вывод

Что выводит: 2, 1, Done! (от цикла), затем снова 2, 1, Done! (от рекурсии) — оба варианта печатают одинаковую последовательность.

"""Рекурсия означает, что на некоторых шагах функция вызывает саму себя.

Рекурсия состоит из

1. Base Case (Базовый случай)
2. Recursive Case (Рекурсивный случай)

Важно: конечная рекурсия должна сходиться к базовому случаю.

Альтернатива рекурсии: итеративная функция, которая с помощью цикла делает то,
что рекурсия осуществляет вызовом самой себя.


Рассмотрим пример итеративной функции обратного отсчёта:

"""Рекурсия означает, что на некоторых шагах функция вызывает саму себя.

Рекурсия состоит из

1. Base Case (Базовый случай)
2. Recursive Case (Рекурсивный случай)

Важно: конечная рекурсия должна сходиться к базовому случаю.

Альтернатива рекурсии: итеративная функция, которая с помощью цикла делает то,
что рекурсия осуществляет вызовом самой себя.


Рассмотрим пример итеративной функции обратного отсчёта:
"""


def countdown_loop(n):
    while True:
        if n > 0:
            print(n)
            n -= 1
        else:
            print("Done!")
            break


countdown_loop(2)


"""Попробуем создать на базе этой итеративной функции рекурсивную функцию:"""


def countdown_recursion(n):
    if n > 0:
        print(n)
        return countdown_recursion(n-1)
    else:
        print("Done!")


countdown_recursion(2)

Переполнение стека: рекурсия без ограничения глубины

less_24__recursion/theory_02_recursion_stack_overflow.py

Та же функция countdown_recursion, что и в предыдущем файле, но вызванная с n=10000 — глубина превышает лимит рекурсии Python (по умолчанию около 1000 вложенных вызовов), и интерпретатор останавливает выполнение с RecursionError. Файл наглядно показывает, что рекурсия — не бесплатная операция: каждый вызов занимает кадр стека, и слишком глубокая рекурсия физически ограничена.

• countdown_recursion(n) — идентична функции из theory_01, без защиты от избыточной глубины
• countdown_recursion(10000) — запуск с большим n
• Печать чисел от 10000 вниз, пока не будет достигнут предел глубины рекурсии Python
• RecursionError с traceback вида '[Previous line repeated N more times]'

Что выводит: Реально наблюдённый запуск (timeout 20с): числа печатались от 10000 вниз примерно до 9003, после чего процесс упал с traceback 'RecursionError: maximum recursion depth exceeded while calling a Python object' и строкой '[Previous line repeated 994 more times]' — то есть лимит глубины рекурсии оказался около 1000 вложенных вызовов countdown_recursion.

"""Пример переполнения стека"""


def countdown_recursion(n):
    if n > 0:
        print(n)
        return countdown_recursion(n - 1)
    else:
        print("Done!")


countdown_recursion(10000)

Сумма списка: нехвостовая рекурсия

less_24__recursion/theory_03_non_tail_recursion_sum_list.py

sum_list(lst) рекурсивно суммирует список: базовый случай — пустой список возвращает 0, рекурсивный — первый элемент плюс сумма остатка списка (lst[0] + sum_list(lst[1:])). Комментарий в конце файла явно объясняет, почему это НЕ хвостовая рекурсия: сложение с lst[0] выполняется уже после того, как рекурсивный вызов вернул результат, то есть рекурсивный вызов — не последнее действие функции.

• sum_list(lst) — базовый случай: if not lst: return 0
• sum_list(lst) — рекурсивный случай: return lst[0] + sum_list(lst[1:])
• Вызовы sum_list([1,2,3,4,5]), sum_list([1]), sum_list([0])
• Комментарий: определение хвостовой (tail) и нехвостовой (non-tail) рекурсии

Что выводит: 15, 1, 0

""" Вычисление суммы списка
Sum list
"""


def sum_list(lst):
    if not lst:
        return 0
    return lst[0] + sum_list(lst[1:])


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

""" Вычисление суммы списка
Sum list
"""


def sum_list(lst):
    if not lst:
        return 0
    return lst[0] + sum_list(lst[1:])


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


""" Кстати, это пример НЕ хвостовой рекурсии: 
вызов рекурсии не является последней операцией в функции, 
так как рекурсивная функция суммируется с lst[0]:

    return lst[0] + factorial_loop(n-1)
    
Ещё раз "на зачёт": 
Хвостовой (tail recursion) называется функция,
последнее действие которой — это именно рекурсивный вызов,  
и после него не остаётся никакой работы.

Если же после вызова рекурсии надо делать ещё что-то, 
то это НЕ хвостовая рекурсия (non-tail recursion).
"""

Сумма списка: хвостовая рекурсия с аккумулятором

less_24__recursion/theory_04_tail_recursion_sum_list.py

sum_list_tail_recursion(lst, accumulator=0) переносит промежуточную сумму в параметр accumulator, поэтому рекурсивный вызов становится последним действием функции — это и есть хвостовая рекурсия, в отличие от предыдущего файла. Результат для тех же входных данных совпадает с нехвостовым вариантом, разница только в механике вычислений (сам Python при этом не выполняет оптимизацию хвостовых вызовов, поэтому выигрыша по стеку на практике нет).

• sum_list_tail_recursion(lst, accumulator=0) — накопитель как параметр по умолчанию
• Базовый случай: if not lst: return accumulator
• Рекурсивный случай: return sum_list_tail_recursion(lst[1:], lst[0] + accumulator) — рекурсия последним действием
• Вызовы на тех же списках [1,2,3,4,5], [1], [0]

Что выводит: 15, 1, 0 — те же результаты, что и в нехвостовом варианте, но вычисляются по-другому.

"""Sum list

Пример хвостовой рекурсии
"""


def sum_list_tail_recursion(lst, accumulator=0):
    if not lst:
        return accumulator
    return sum_list_tail_recursion(lst[1:], lst[0] + accumulator)


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

Ханойские башни: рекурсивное решение с визуализацией

less_24__recursion/theory_05_example_decision_Tower_of_Hanoi_by_recursion.py

Классическая задача 'разделяй и властвуй': hanoi(n, source, target, auxiliary, ...) перемещает n-1 дисков на вспомогательный стержень, переносит самый большой диск на целевой, затем переносит n-1 дисков со вспомогательного на целевой — всё через рекурсивные вызовы самой себя. draw_towers() очищает экран и рисует цветные ASCII-башни, а input() после каждого хода ждёт нажатия Enter, поэтому файл явно помечен комментарием, что запускать его нужно в терминале ОС, а не в IDE.

• get_color(disk) — подбирает ANSI-цвет по номеру диска
• draw_towers(towers, total_height) — очищает экран (os.system('cls'/'clear')) и рисует три башни
• hanoi(n, source, target, auxiliary, towers, total_height) — базовый случай n == 0 (неявно, через if n > 0), два рекурсивных вызова вокруг перемещения самого большого диска
• input('For the next move - press "Enter"!') — блокирует выполнение до нажатия Enter
• num_disks = 6 — начальная конфигурация трёх башен

Что выводит: Реально наблюдённый запуск с пустым stdin (timeout 10с): скрипт нарисовал начальную конфигурацию из 6 дисков, выполнил первый ход (диск 1 с башни 0 на башню 2), перерисовал башни и вывел приглашение 'For the next move - press "Enter"!', после чего немедленно упал с 'EOFError: EOF when reading a line' — так как input() не получил данных. Это подтверждает предупреждение в файле: без интерактивного терминала скрипт не может работать дальше первого хода.

"""Tower of Hanoi

https://upload.wikimedia.org/wikipedia/commons/6/60/Tower_of_Hanoi_4.gif?20050322192703

Идея рекурсивной функции для решения задачи Ханойских башен основывается на разбиении задачи на более простые подзадачи.
В частности, перемещение n дисков с одного стержня на другой можно свести к последовательности шагов,
каждый из которых решает меньшую задачу.

Вот основные шаги и принципы, лежащие в основе рекурсивного алгоритма:

    Базовый случай: Если у нас только один диск, переместить его напрямую с исходного стержня на целевой.
    Рекурсивный случай: Если дисков больше одного:
        Переместить n-1 дисков с исходного стержня на вспомогательный, используя целевой стержень как вспомогательный.
        Переместить оставшийся (самый большой) диск с исходного стержня на целевой.

"""Tower of Hanoi

https://upload.wikimedia.org/wikipedia/commons/6/60/Tower_of_Hanoi_4.gif?20050322192703

Идея рекурсивной функции для решения задачи Ханойских башен основывается на разбиении задачи на более простые подзадачи.
В частности, перемещение n дисков с одного стержня на другой можно свести к последовательности шагов,
каждый из которых решает меньшую задачу.

Вот основные шаги и принципы, лежащие в основе рекурсивного алгоритма:

    Базовый случай: Если у нас только один диск, переместить его напрямую с исходного стержня на целевой.
    Рекурсивный случай: Если дисков больше одного:
        Переместить n-1 дисков с исходного стержня на вспомогательный, используя целевой стержень как вспомогательный.
        Переместить оставшийся (самый большой) диск с исходного стержня на целевой.
        Переместить n-1 дисков с вспомогательного стержня на целевой, используя исходный стержень как вспомогательный.

(ВНИМЕНИЕ! Для запуска скрипта необходимо использовать терминал ОС, а не IDE!)
"""

import os
import time


def clear_screen():
    # Windows
    if os.name == 'nt':
        os.system('cls')
    # Unix/Linux/MacOS/BSD/etc
    else:
        os.system('clear')


def get_color(disk):
    colors = [
        "\033[31m",  # Красный
        "\033[32m",  # Зеленый
        "\033[33m",  # Желтый
        "\033[34m",  # Синий
        "\033[35m",  # Фиолетовый
        "\033[36m",  # Голубой
    ]
    return colors[(disk - 1) % len(colors)]


def draw_towers(towers, total_height):
    clear_screen()
    for i in range(total_height - 1, -1, -1):
        for tower in towers:
            if i < len(tower):
                disk = tower[i]
                color = get_color(disk)
                print(color + str(disk).center(10) + "\033[0m", end=' ')
            else:
                print('|'.center(10), end=' ')
        print()
    print('-' * 30)


def hanoi(n, source, target, auxiliary, towers, total_height):
    if n > 0:
        hanoi(n - 1, source, auxiliary, target, towers, total_height)

        disk = towers[source].pop()
        towers[target].append(disk)
        draw_towers(towers, total_height)
        time.sleep(1)
        input('For the next move - press "Enter"!')

        hanoi(n - 1, auxiliary, target, source, towers, total_height)


# Начальные условия
num_disks = 6  # Можно изменить количество дисков
towers = [list(range(num_disks, 0, -1)), [], []]
total_height = num_disks + 1  # Высота должна включать стержень
draw_towers(towers, total_height)
time.sleep(1)
hanoi(num_disks, 0, 2, 1, towers, total_height)

Что выведет код? Рекурсия без базового случая

less_24__recursion/theory_06_what_will_this_code_do.py

message() вызывает саму себя безусловно, без единого параметра и без проверки на остановку — то есть у рекурсии нет базового случая, и функция принципиально не может завершиться сама. Файл — часть серии 'что выведет этот код' и наглядно показывает: единственная причина, по которой выполнение вообще останавливается, — исчерпание лимита глубины рекурсии Python и исключение RecursionError.

• message() — печатает строку и сразу же вызывает message() без аргументов и без условия
• Нет базового случая: рекурсия не сходится ни к какому состоянию остановки
• message() — первый вызов запускает бесконечную (по замыслу) цепочку вызовов
• RecursionError с '[Previous line repeated N more times]' как единственный способ остановки

Что выводит: Реально наблюдённый запуск (timeout 15с, пустой stdin): строка 'Это рекурсивная функция' печаталась около тысячи раз подряд, после чего процесс упал с traceback '[Previous line repeated 994 more times]' и 'RecursionError: maximum recursion depth exceeded while calling a Python object'.

""" What will this code do? """


def message():
    print('Это рекурсивная функция')
    message()


message()

Что выведет код? Печать до рекурсивного вызова

less_24__recursion/theory_07_what_will_this_code_do.py

message(times) сначала печатает текст и значение times, и только потом вызывает message(times - 1). Поскольку печать происходит до рекурсивного спуска, числа выводятся в порядке убывания (5, 4, 3, 2, 1) — ровно в том порядке, в каком функция вызывается 'вглубь'. Базовый случай — неявная остановка по условию times > 0.

• message(times) — базовый случай: тело выполняется только при times > 0
• print('Это рекурсивная функция') и print(times) — до рекурсивного вызова
• message(times - 1) — рекурсивный вызов после обеих печатей
• message(5) — стартовый вызов

Что выводит: Пять пар строк 'Это рекурсивная функция' / число, числа идут по убыванию: 5, 4, 3, 2, 1.

""" What will this code do? """


def message(times):
    if times > 0:
        print('Это рекурсивная функция')
        print(times)
        message(times - 1)


message(5)

Что выведет код? Печать после рекурсивного вызова

less_24__recursion/theory_08_what_will_this_code_do.py

message(times) сначала полностью уходит в рекурсию (message(times - 1)) и только после того, как вложенный вызов вернулся, печатает times. Из-за этого print('Это рекурсивная функция') выполняется на каждом уровне спуска сразу, а print(times) — только во время 'разворачивания' стека, поэтому числа печатаются в порядке возрастания (1, 2, 3, 4, 5) — в противоположность theory_07.

• message(times) — базовый случай: тело выполняется только при times > 0
• print('Это рекурсивная функция') — печатается на каждом уровне спуска
• message(times - 1) — рекурсивный вызов ДО print(times)
• print(times) — выполняется уже при возврате из вложенного вызова (на разворачивании стека)
• message(5) — стартовый вызов

Что выводит: Сначала пять раз подряд 'Это рекурсивная функция' (все вызовы уходят вглубь до печати чисел), затем числа по возрастанию: 1, 2, 3, 4, 5.

""" What will this code do? """


def message(times):
    if times > 0:
        print('Это рекурсивная функция')
        message(times - 1)
        print(times)


message(5)

isinstance(): проверка типа объекта

less_24__recursion/theory_09__isinstance.md

Краткая справка по предикату isinstance(object, classinfo), который проверяет, является ли объект экземпляром указанного класса. Отмечает две особенности: можно проверять сразу несколько типов, передав кортеж классов вторым аргументом, и функция учитывает наследование — экземпляр дочернего класса считается экземпляром и родительского тоже.

• isinstance(object, classinfo) — базовая сигнатура
• isinstance(x, int) / isinstance(x, float) — проверка одного типа
• isinstance(x, (int, float)) — проверка сразу нескольких типов через кортеж
• Учёт наследования: объект дочернего класса — тоже экземпляр родительского

Функция-предикат **`isinstance()`** используется для проверки, 
является ли объект экземпляром указанного класса (набора классов). 


```python
isinstance(object, classinfo)
```

* **`object`** — объект, который проверяется.
* **`classinfo`** — класс или тюпл классов, с которым сравнивается объект.

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

```python
x = 10
print(isinstance(x, int))       # True, потому что x — целое число
print(isinstance(x, float))     # False, x не float
print(isinstance(x, (int, float)))  # True, проверяем несколько типов
```

Особенности:

1. Можно проверять на несколько типов сразу, передавая кортеж классов.
2. Функция учитывает наследование (объект ребёнка тоже будет считаться экземпляром родителя).