### HW_02: Рекурсия

# Вопрос 1.
def g(n):
    """Возвращает значение G(n), вычисленное рекурсивно.
    >>> g(1)
    1
    >>> g(2)
    2
    >>> g(3)
    3
    >>> g(4)
    10
    >>> g(5)
    22
    """
    if n <= 3:
        return n
    return g(n - 1) + 2 * g(n - 2) + 3 * g(n - 3)


def g_iter(n):
    """Возвращает значение G(n), вычисленное итеративно.
    >>> g_iter(1)
    1
    >>> g_iter(2)
    2
    >>> g_iter(3)
    3
    >>> g_iter(4)
    10
    >>> g_iter(5)
    22
    """
    if n <= 3:
        return n
    a, b, c = 1, 2, 3           # G(1), G(2), G(3)
    for _ in range(n - 3):
        a, b, c = b, c, c + 2 * b + 3 * a
    return c


# Вопрос 2.
def has_seven(k):
    """Проверка наличия цифры 7 в k
    >>> has_seven(3)
    False
    >>> has_seven(7)
    True
    >>> has_seven(2734)
    True
    >>> has_seven(2634)
    False
    >>> has_seven(734)
    True
    >>> has_seven(7777)
    True
    """
    if k % 10 == 7:
        return True
    elif k < 10:
        return False
    return has_seven(k // 10)


# Вопрос 3.
"1 2 3 4 5 6 [7] 6 5 4 3 2 1 [0] 1 2 [3] 2 1 0 [-1] 0 1 2 3 4 [5] [4] 5 6"
def pingpong(n):
    """Возвращает n-ый элемент последовательности «пинг-понг».
    >>> pingpong(7)
    7
    >>> pingpong(8)
    6
    >>> pingpong(15)
    1
    >>> pingpong(21)
    -1
    >>> pingpong(22)
    0
    >>> pingpong(30)
    6
    >>> pingpong(68)
    2
    >>> pingpong(69)
    1
    >>> pingpong(70)
    0
    >>> pingpong(71)
    1
    >>> pingpong(72)
    0
    >>> pingpong(100)
    2
    """
    def helper(i, val, direction):
        if i == n:
            return val
        new_dir = -direction if (has_seven(i) or i % 7 == 0) else direction
        return helper(i + 1, val + new_dir, new_dir)
    return helper(1, 1, 1)


# Вопрос 4.
def ten_pairs(n):
    """Возвращает число пар цифр в положительном целом n, в сумме образующих 10.
    >>> ten_pairs(7823952)
    3
    >>> ten_pairs(55055)
    6
    >>> ten_pairs(9641469)
    6
    """
    def count_digit(n, d):
        """Сколько раз цифра d встречается в числе n."""
        if n == 0:
            return 0
        return (1 if n % 10 == d else 0) + count_digit(n // 10, d)

    if n < 10:
        return 0
    # Считаем сколько «партнёров» последней цифры есть среди остальных,
    # затем рекурсивно решаем задачу для числа без последней цифры.
    return count_digit(n // 10, 10 - n % 10) + ten_pairs(n // 10)


# Вопрос 5.
def count_change(amount):
    """Возвращает количество способов размена amount киберденьгами.
    >>> count_change(7)
    6
    >>> count_change(10)
    14
    >>> count_change(20)
    60
    >>> count_change(100)
    9828
    """
    def helper(remaining, coin):
        if remaining == 0:
            return 1
        if remaining < 0 or coin > remaining:
            return 0
        # Берём текущую монету ещё раз ИЛИ переходим к следующей (номинал ×2)
        return helper(remaining - coin, coin) + helper(remaining, coin * 2)
    return helper(amount, 1)


# Вопрос 6.
from operator import sub, mul

def make_anonymous_factorial():
    """Возвращает выражение, вычисляющее факториал.
    >>> make_anonymous_factorial()(5)
    120
    """
    # Y-комбинатор: функция вызывает саму себя через аргумент f,
    # не используя никакого имени.
    return (lambda f: f(f))(
        lambda f: lambda n: 1 if n == 0 else mul(n, f(f)(sub(n, 1)))
    )