Рекурсія та модульна структура

Великі задачі зручніше розв'язувати, коли складну дію можна виразити через простіший варіант тієї самої дії, а програму - розділити на файли з чіткими обов'язками. Перша ідея приводить до рекурсії, друга - до модулів.

Цілі лекції

Після опрацювання матеріалу ви зможете:

• пояснювати рекурсію, базовий випадок і рекурсивний крок;
• простежувати рекурсивні виклики за допомогою моделі стека;
• перевіряти, чи наближається рекурсія до завершення;
• порівнювати рекурсивний та ітеративний способи розв'язання задачі;
• імпортувати модулі Python різними способами та задавати псевдоніми;
• використовувати початкові можливості стандартних модулів math і random;
• створювати власний модуль і відокремлювати його перевірку від імпорту;
• пояснювати призначення умови if __name__ == "__main__".

Передумови

Потрібно знати, як у Python оголосити й викликати функцію, передати аргумент, повернути значення через return, використати умову if і цикл for або while. Корисно пам'ятати, що кожен виклик функції має власні локальні змінні.

1. Функція викликає саму себе

Рекурсія - це спосіб організації обчислення, за якого функція прямо або опосередковано викликає саму себе для простішого варіанта задачі.

Коректна рекурсивна функція має дві обов'язкові частини:

1. Базовий випадок повертає результат без нового рекурсивного виклику.
2. Рекурсивний крок зводить задачу до меншої та викликає функцію з новими даними.

Крім наявності цих частин, потрібно довести, що кожен крок наближає аргумент до базового випадку. Інакше функція не завершиться нормально.

Приклад: факторіал

Факторіал невід'ємного цілого числа визначають так:

0! = 1
n! = n * (n - 1)!, якщо n > 0

У визначенні вже видно рекурсивну структуру. Для n = 0 маємо базовий випадок, а для більшого n використовуємо факторіал меншого числа.

def factorial(n):
    if n < 0:
        raise ValueError("n має бути невід'ємним")
    if n <= 1:                 # базовий випадок
        return 1
    return n * factorial(n - 1)  # рекурсивний крок


print(factorial(5))

Результат усіх трьох програм:

120

Перевірка n < 0 не є базовим випадком математичного обчислення. Вона відхиляє вхідні дані, для яких функцію не визначено. Базові випадки n = 0 і n = 1 повертають 1.

2. Як працює стек викликів

Коли функція викликає іншу функцію, поточний виклик ще не завершено. Середовище виконання має пам'ятати:

• значення його параметрів і локальних змінних;
• місце програми, до якого треба повернутися;
• яку незавершену операцію потрібно продовжити.

Ці відомості зберігаються у стеку викликів. Стек можна уявити як стопку карток: новий виклик кладуть зверху, а після return верхню картку знімають. Першим завершується останній створений виклик.

Для factorial(4) виклики спочатку заглиблюються:

factorial(4)
  -> factorial(3)
       -> factorial(2)
            -> factorial(1)

У момент досягнення базового випадку стек можна подати так:

верх стека  | factorial(1): повернути 1
            | factorial(2): очікує 2 * результат
            | factorial(3): очікує 3 * результат
низ стека   | factorial(4): очікує 4 * результат

Після цього результати повертаються у зворотному порядку:

Важливо розрізняти виклики й функцію. Код функції один, але одночасно в стеку можуть існувати кілька її незавершених викликів, кожен зі своїм значенням n.

3. Глибина, завершення і помилки

Глибина рекурсії - кількість активних рекурсивних викликів у ланцюжку. Вона витрачає пам'ять стека. Python навмисно обмежує максимальну глибину, тому дуже довгий ланцюжок зазвичай завершується помилкою RecursionError, а не працює нескінченно.

Типова помилка:

def countdown(n):
    if n == 0:
        return
    print(n)
    countdown(n + 1)  # помилка: віддаляємося від нуля

Базовий випадок тут записано, але для додатного n він недосяжний: значення збільшується. Правильний крок для такого відліку - countdown(n - 1).

Перед запуском рекурсивної функції дайте відповіді на три запитання:

1. Які вхідні дані одразу дають відомий результат?
2. Як кожен наступний виклик спрощує задачу?
3. Чому після скінченної кількості кроків буде досягнуто базового випадку?

Не варто виправляти неправильний алгоритм простим збільшенням ліміту рекурсії. Спочатку потрібно перевірити базовий випадок, напрям зміни аргументу й очікувану глибину.

4. Рекурсивна сума вимірювань

Нехай прилад повернув кілька значень освітленості. Суму можна визначити рекурсивно: сума порожньої послідовності дорівнює нулю, а сума непорожньої - першому значенню плюс сума решти.

def measurement_sum(values):
    if not values:
        return 0.0
    return values[0] + measurement_sum(values[1:])


illuminance_lx = [120.5, 118.0, 121.5]
print(measurement_sum(illuminance_lx))

Очікуваний результат:

360

Цей приклад добре показує структуру, але в Python зріз values[1:] щоразу створює новий список. Для великої кількості вимірювань звичайний цикл або вбудована функція sum(values) буде простішою й практичнішою.

5. Рекурсія чи ітерація

Багато задач можна розв'язати і рекурсивно, і за допомогою циклу. Ітерація повторює дії циклом і зазвичай не створює нового виклику функції на кожному кроці.

Ітеративний факторіал:

def factorial_iterative(n):
    if n < 0:
        raise ValueError("n має бути невід'ємним")

    result = 1
    for value in range(2, n + 1):
        result *= value
    return result


print(factorial_iterative(5))

Рекурсія не є автоматично «кращою» або «розумнішою». Вибирайте її, коли вона робить структуру алгоритму зрозумілішою і глибина є контрольованою. Для простого факторіала чи суми довгого списку в Python зазвичай доцільніша ітерація.

6. Навіщо програмі модулі

Коли весь код міститься в одному файлі, складно відрізнити загальні обчислення від запуску конкретного сценарію. Модуль Python - це файл .py, який містить функції, константи та інші визначення і який можна імпортувати в інший файл.

Модулі допомагають:

• групувати пов'язані дії;
• повторно використовувати функції;
• давати зрозумілі простори імен;
• окремо перевіряти частини програми;
• зменшувати розмір головного файла.

У курсах C і C++ часто пояснюють поділ на заголовковий файл .h з оголошеннями та файл .cpp з реалізаціями. У Python початкова модель інша: окремий файл .py уже є модулем, а його функції доступні після імпорту. Нам не потрібно вручну дублювати сигнатуру функції в заголовку. Це адаптація тієї самої інженерної ідеї поділу відповідальності, а не буквальне відтворення структури C++.

7. Способи імпорту в Python

Імпорт модуля

import math

angle_rad = math.radians(30)
signal_component = math.sin(angle_rad)
print(signal_component)

Ім'я math показує походження функцій. Такий запис особливо зрозумілий, коли у програмі кілька модулів.

Імпорт окремих імен

from math import radians, sin

angle_rad = radians(30)
signal_component = sin(angle_rad)

Запис коротший, але з місця виклику вже не видно, що sin належить модулю math. Імпортуйте лише потрібні імена. Конструкції from module import * варто уникати: вона може непомітно замінити наявні імена.

Псевдонім

import random as rnd

wavelengths_nm = [450, 532, 650]
print(rnd.choice(wavelengths_nm))

Ключове слово as задає локальний псевдонім. Він корисний для довгих або загальноприйнято скорочуваних назв, але скорочення має залишатися зрозумілим.

Ці форми відповідають різним способам звернення до імен:

8. Стандартні модулі math і random

Стандартна бібліотека постачається разом із Python. Для math і random не потрібно окремо завантажувати пакет.

Модуль math містить математичні функції та константи: sqrt, sin, cos, radians, pi та інші. Модуль random створює псевдовипадкові значення, наприклад для моделювання шуму або випадкового вибору тестового режиму.

import math
import random

rng = random.Random(175)
angle_deg = 30
ideal_signal = math.sin(math.radians(angle_deg))
noise = rng.uniform(-0.01, 0.01)

print(f"Ідеальний сигнал: {ideal_signal:.3f}")
print(f"З шумом: {ideal_signal + noise:.3f}")

У всіх мовах приклад поєднує математичну функцію з генератором псевдовипадкових чисел. Однакове початкове значення генератора допомагає повторювати експеримент у межах тієї самої реалізації, але різні мови не зобов'язані генерувати однакову послідовність.

random не моделює фізичний шум автоматично: розробник сам обирає розподіл і межі відповідно до задачі. Цей модуль також не призначений для криптографічних ключів і паролів.

9. Власний модуль

Створимо два файли в одній папці:

optics_project/
  optics.py
  main.py

Файл optics.py містить повторно використовуване обчислення:

# optics.py
import math


def degrees_to_signal(angle_deg):
    """Повертає sin кута, заданого у градусах."""
    return math.sin(math.radians(angle_deg))

Файл main.py імпортує модуль і запускає сценарій:

# main.py
import optics


angle_deg = 30
signal = optics.degrees_to_signal(angle_deg)
print(f"Складова сигналу: {signal:.3f}")

Запуск:

python main.py

Очікуваний результат:

Складова сигналу: 0.500

Цей багатофайловий приклад навмисно подано лише для Python. Scala і Go також мають модулі та простори імен, але організовують файли й точку входу за іншими правилами. Спільні вкладки тут створили б хибне враження, що достатньо механічно замінити синтаксис.

Імпорт виконує верхньорівневі команди модуля. Тому в модулі краще зберігати визначення, а не код, який безумовно запитує дані або запускає довге обчислення.

10. Умова if __name__ == "__main__"

Python автоматично задає спеціальну змінну __name__:

• якщо файл запущено як головну програму, __name__ дорівнює "__main__";
• якщо файл імпортовано, __name__ зазвичай дорівнює імені модуля.

Це дає змогу поєднати корисні визначення з короткою демонстрацією:

# optics.py
import math


def degrees_to_signal(angle_deg):
    return math.sin(math.radians(angle_deg))


if __name__ == "__main__":
    print(degrees_to_signal(30))

Команда python optics.py виведе результат перевірки. Натомість під час import optics функцію буде визначено, але демонстраційний print не виконається.

Умова не «робить файл модулем»: будь-який відповідний файл .py уже може бути модулем. Вона лише відділяє поведінку прямого запуску від поведінки під час імпорту.

Підсумок

• Рекурсивна функція розв'язує задачу через простіший варіант тієї самої задачі.
• Базовий випадок завершує ланцюжок, а рекурсивний крок має наближати дані до нього.
• Стек викликів зберігає незавершені виклики; результати повертаються у зворотному порядку.
• Велика або неправильна рекурсія витрачає стек і в Python може спричинити RecursionError.
• Рекурсія доречна, коли відображає структуру задачі; для простого повторення часто кращий цикл.
• Модуль Python - це файл .py із визначеннями, які можна імпортувати.
• import module, from module import name та import module as alias по-різному додають імена до програми.
• math надає математичні засоби, а random - засоби псевдовипадкового моделювання.
• Власний модуль відокремлює повторно використовувану логіку від головного сценарію.
• Умова if __name__ == "__main__" запускає демонстраційний або головний код лише під час прямого запуску файла.