9.2. Подпрограммы и рекурсия

Функции в Python

Функция — это именованный блок кода, который можно вызывать многократно.

Определение функции начинается с ключевого слова def:

def имя_функции(параметры):
    """документация (необязательно)"""
    тело функции
    return результат

Пример:

def say_hello(name):
    """Приветствие."""
    print(f"Привет, {name}!")

say_hello("Анна")  # Привет, Анна!

Параметры и возврат значений

Функция с параметрами:

def sum_two(a, b):
    return a + b

result = sum_two(5, 3)  # 8

Несколько параметров:

def max_of_three(x, y, z):
    """Возвращает максимум из трёх чисел."""
    if x >= y and x >= z:
        return x
    elif y >= z:
        return y
    else:
        return z

Параметры по умолчанию:

def power(x, n=2):
    """Возводит x в степень n (по умолчанию квадрат)."""
    return x ** n

print(power(5))     # 25
print(power(5, 3))  # 125

Локальные и глобальные переменные

Глобальные переменные — объявлены вне функций, доступны везде.

Локальные переменные — объявлены внутри функции, доступны только в ней.

x = 10  # глобальная переменная

def func():
    x = 5  # локальная переменная (не изменяет глобальную!)
    print("Внутри:", x)

func()
print("Снаружи:", x)

# Вывод:
# Внутри: 5
# Снаружи: 10

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

Рекурсия — это способ решения задачи, при котором функция вызывает саму себя.

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

• Базовый случай — условие прекращения рекурсии
• Рекурсивный шаг — вызов функции с изменёнными параметрами

Пример: вычисление факториала

def factorial(n):
    """Вычисляет n! рекурсивно."""
    # Базовый случай
    if n <= 1:
        return 1
    # Рекурсивный шаг
    return n * factorial(n - 1)

print(factorial(5))  # 120

Пример: числа Фибоначчи

def fibonacci(n):
    """Возвращает n-е число Фибоначчи."""
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

# 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...
print(fibonacci(7))  # 13

Лямбда-функции и функции высшего порядка

Лямбда-функция — это анонимная функция, заданная выражением. Используется для простых операций.

Синтаксис:

# Обычная функция
def square(x):
    return x ** 2

# Лямбда-функция
square = lambda x: x ** 2

print(square(5))  # 25

Лямбда с несколькими параметрами:

add = lambda a, b: a + b
print(add(3, 4))  # 7

# Сортировка кортежей по второму элементу
pairs = [(1, 'b'), (2, 'a'), (3, 'c')]
pairs.sort(key=lambda p: p[1])
print(pairs)  # [(2, 'a'), (1, 'b'), (3, 'c')]

Функции высшего порядка:

Функция высшего порядка — это функция, которая принимает другие функции как аргументы или возвращает их.

# map — применение функции к каждому элементу
numbers = [1, 2, 3, 4, 5]
squares = list(map(lambda x: x**2, numbers))
print(squares)  # [1, 4, 9, 16, 25]

# filter — фильтрация элементов
even = list(filter(lambda x: x % 2 == 0, numbers))
print(even)  # [2, 4]

# sorted с ключом
words = ['banana', 'apple', 'cherry']
sorted_words = sorted(words, key=lambda w: len(w))
print(sorted_words)  # ['apple', 'banana', 'cherry']

Практические задачи на рекурсию

Задача 1: Сумма цифр числа

def digit_sum(n):
    """Возвращает сумму цифр числа."""
    if n < 10:
        return n
    return n % 10 + digit_sum(n // 10)

print(digit_sum(12345))  # 15

Задача 2: Бинарный поиск (рекурсивный)

def binary_search(arr, target, left=0, right=None):
    """Ищет элемент в отсортированном массиве."""
    if right is None:
        right = len(arr) - 1
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)
    else:
        return binary_search(arr, target, left, mid - 1)

a = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(a, 7))  # 3

Задача 3: Быстрое возведение в степень

def power(base, exp):
    """Возводит base в степень exp за O(log n)."""
    if exp == 0:
        return 1
    if exp % 2 == 0:
        half = power(base, exp // 2)
        return half * half
    return base * power(base, exp - 1)

print(power(2, 10))  # 1024

Задача 4: Ханойские башни

def hanoi(n, source='A', target='C', helper='B'):
    """Решение задачи о ханойских башнях."""
    if n == 1:
        print(f"Переместить диск 1 с {source} на {target}")
        return
    hanoi(n-1, source, helper, target)
    print(f"Переместить диск {n} с {source} на {target}")
    hanoi(n-1, helper, target, source)

hanoi(3)

Задача 5: Генерация всех перестановок

def permutations(s):
    """Генерирует все перестановки строки."""
    if len(s) <= 1:
        return [s]
    result = []
    for i, char in enumerate(s):
        for perm in permutations(s[:i] + s[i+1:]):
            result.append(char + perm)
    return result

print(permutations("abc"))