### Лабораторная работа № 3: Рекурсия

# Вопрос 1
def sum(n):
    """Вычисляет сумму всех положительных целых от 1 до n включительно.
    Считай, что n >= 0.

    >>> sum(1)
    1
    >>> sum(5)  # 1 + 2 + 3 + 4 + 5
    15
    """
    if n == 0:
        return 0
    return n + sum(n - 1)


# Подвопрос 2.1
def sum_every_other_number(n):
    """Возвращает частичную сумму натуральных чисел до n включительно,
    в которую числа входят через одно.

    >>> sum_every_other_number(8)
    20
    >>> sum_every_other_number(9)
    25
    """
    if n == 0:
        return 0
    elif n == 1:   # ИСПРАВЛЕНИЕ: добавлен базовый случай для n=1,
        return 1   # иначе n-2 = -1 уйдёт в бесконечную рекурсию
    else:
        return n + sum_every_other_number(n - 2)


# Подвопрос 2.2
def fibonacci(n):
    """Возвращает n-ое число Фибоначчи.

    >>> fibonacci(11)
    89
    """
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)  # ИСПРАВЛЕНИЕ: добавлен return


# Подвопрос 2.3
def even_digits(n):
    """Возвращает долю чётных цифр в числе n.

    >>> even_digits(23479837)  # 3 / 8
    0.375
    """
    # ИСПРАВЛЕНИЕ: полностью переписана. Вспомогательная функция считает
    # (кол-во цифр, кол-во чётных цифр) рекурсивно, а затем вычисляется доля.
    def helper(n):
        """Возвращает (всего цифр, чётных цифр)."""
        if n == 0:
            return (0, 0)
        digits, evens = helper(n // 10)
        if (n % 10) % 2 == 0:
            return (digits + 1, evens + 1)
        return (digits + 1, evens)

    total, even = helper(n)
    return even / total


# Вопрос 3
def hailstone(n):
    """Выводит последовательность чисел-градин. Возвращает кол-во элементов.

    >>> a = hailstone(10)
    10
    5
    16
    8
    4
    2
    1
    >>> a
    7
    """
    print(n)
    if n == 1:
        return 1
    elif n % 2 == 0:
        return 1 + hailstone(n // 2)
    else:
        return 1 + hailstone(3 * n + 1)


# Вопрос 4
def gcd(a, b):
    """Возвращает НОД для a и b. Нужно использовать рекурсию.

    >>> gcd(34, 19)
    1
    >>> gcd(39, 91)
    13
    >>> gcd(20, 30)
    10
    >>> gcd(40, 40)
    40
    """
    # Приводим к виду a >= b
    if a < b:
        a, b = b, a
    if a % b == 0:
        return b
    return gcd(b, a % b)


# Вопрос 5
def paths(m, n):
    """Вычисляет количество путей из одного угла в другой на поле M на N.

    >>> paths(2, 2)
    2
    >>> paths(5, 7)
    210
    >>> paths(117, 1)
    1
    >>> paths(1, 157)
    1
    """
    # Базовый случай: единственный столбец или строка — только один путь
    if m == 1 or n == 1:
        return 1
    # Из любой клетки можно прийти только снизу или слева
    return paths(m - 1, n) + paths(m, n - 1)


# Вопрос 6
def print_move(origin, destination):
    """Печатает информацию о перемещении диска."""
    print("Перемещение диска со стержня", origin, "на стержень", destination)

def move_stack(n, start, end):
    """Выводит последовательность перемещений n дисков с начального стержня
    на конечный в соответствии с правилами Ханойских башен.

    >>> move_stack(1, 1, 3)
    Перемещение диска со стержня 1 на стержень 3
    >>> move_stack(2, 1, 3)
    Перемещение диска со стержня 1 на стержень 2
    Перемещение диска со стержня 1 на стержень 3
    Перемещение диска со стержня 2 на стержень 3
    >>> move_stack(3, 1, 3)
    Перемещение диска со стержня 1 на стержень 3
    Перемещение диска со стержня 1 на стержень 2
    Перемещение диска со стержня 3 на стержень 2
    Перемещение диска со стержня 1 на стержень 3
    Перемещение диска со стержня 2 на стержень 1
    Перемещение диска со стержня 2 на стержень 3
    Перемещение диска со стержня 1 на стержень 3
    """
    assert 1 <= start <= 3 and 1 <= end <= 3 and start != end, "Плохие аргументы"
    if n == 1:
        print_move(start, end)
    else:
        # Вспомогательный стержень — тот, что не start и не end
        middle = 6 - start - end  # сумма 1+2+3=6, вычитаем два известных
        move_stack(n - 1, start, middle)  # переносим верхние n-1 дисков на aux
        print_move(start, end)            # переносим самый большой диск
        move_stack(n - 1, middle, end)    # переносим n-1 дисков с aux на end