Лаб. 03: Рекурсия

Теория

Рекурсивная функция — это функция, вызывающая саму себя, прямо или косвенно. Такие функции состоят из трёх важных компонент:

Базовые случаи — решение наиболее простой формы решаемой задачи.
Рекурсивные случаи — вызовы в ходе вычисления функцией самой себя с более простыми аргументами.
Использование рекурсивных вызовов для решения всей задачи.

Посмотри на канонический пример, функцию factorial:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

Всем известно, что \(0!\) равен \(1\) по определению. Таким образом, здесь базовым случаем выбран вариант \(n = 0\). Рекурсивный случай так же следует из определения:

\[n! = n\cdot (n-1)!\]

В последующих заданиях тебе придётся создавать рекурсивные функции. Вот несколько общих советов:

Обдумывай, как решить задачу, имея ответы на упрощённые версии текущей задачи. Доверяй рекурсии — предполагай, что решение упрощенной версии просто существует, не важно, как оно получается.
Определи, какой результат будет в самом простом случае задачи. Это станет базовым случаем — точкой останова рекурсии. Проверь, не упускаешь ли ты другие возможные базовые случаи (кстати, распространённая ошибка).
Возможно тебе поможет решение задачи в итеративном стиле, а затем отыщется и рекурсивный вариант.

Основная часть

Эту часть практических вопросов нужно успеть сделать на занятии.

После завершения работы над каждым вопросом фиксируй измененият (делай коммит):

$ git add .
$ git commit -m "Решение вопроса X"

Так же не возбраняется в любое время проталкивать изменения на GitHub:

$ git push

Вопрос 1: В сумме

Напиши функцию sum, которая принимает единственный аргумент n и вычисляет сумму всех целых чисел от 1 до n включительно. Считай, что n — неотрицательное целое число.

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

    >>> sum(1)
    1
    >>> sum(5)  # 1 + 2 + 3 + 4 + 5
    15
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Вопрос 2: Непонимание

Следующие примеры реализации рекурсии отражают наиболее распространённые ошибки, вызванные непониманием. Исправь их.

Подвопрос 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
    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:
        fibonacci(n - 1) + fibonacci(n - 2)

Подвопрос 2.3

Вот это совсем непростая задачка! С первого раза может и не поддаться.

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

    >>> even_digits(23479837) # 3 / 8
    0.375
    """
    if n == 0:
        return num_digits / num_evens
    num_digits, num_evens = 0, 0
    if n % 2 == 0:
        counter += 1
    num_evens += 1
    return (even_digits(n // 10) + num_evens) / counter

Вопрос 3: Числа-градины

Напиши рекурсивную версию функции hailstone из первой домашней работы.

def hailstone(n):
    """Выводит последовательность чисел-градин, начинающуюся с n, и возвращает её длину.

    >>> a = hailstone(10)
    10
    5
    16
    8
    4
    2
    1
    >>> a
    7
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Вопрос 4*: НОД

Наибольшим общим делителем (НОД) двух положительных целых чисел a и b называют такое наибольшее целое число, которое делит оба из них без остатка. Древнегреческий математик Евклид за 300 лет до нашей эры осознал, что наибольшим общим делителем для a и b является:

меньшее значение, если оно делит большее без остатка, ИЛИ
НОД меньшего значения и остатка от деления большего на меньшее, то есть если a > b и a не делится на b, то gcd(a, b) == gcd(b, a % b).

Напиши рекурсивную функцию gcd используя алгоритм Евклида.

def gcd(a, b):
    """Возвращает наибольший общий делитель для a и b.

    >>> gcd(34, 19)
    1
    >>> gcd(39, 91)
    13
    >>> gcd(20, 30)
    10
    >>> gcd(40, 40)
    40
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Дополнительная часть

Эту часть нужно поделать и дома. Конечно, если ещё есть силы.

Вопрос 5*: Комбинаторика насекомых

Представь насекомое на клетчатом поле размера m x n. Насекомое стартует из нижнего левого угла (0, 0) и хочет попасть в правый верхний угол (m-1, n-1). Насекомое может двигаться только вверх или направо. Напиши функцию paths, которая принимает размеры поля и возвращает число различных путей для насекомого из начальной точки в конечную.

Существует решение в замкнутой форме, но тут требуется рекурсия.

Например, поле 2 на 2 имеет всего два варианта движения, поле 3 на 3 содержит 6 различных путей (на рисунке отображено только 3).

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

    >>> paths(2, 2)
    2
    >>> paths(5, 7)
    210
    >>> paths(117, 1)
    1
    >>> paths(1, 157)
    1
    """
    "*** ТВОЙ КОД ЗДЕСЬ ***"

Вопрос 6*: Ханойские башни

В великом храме города Бенарес, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены три алмазных стержня высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времён, монахи этого монастыря провинились перед богом Брахмой. Разгневанный Брахма воздвиг три высоких стержня и на один из них возложил 64 диска, сделанных из чистого золота, причём так, что каждый меньший диск может лежать только на большем. Как только все диски будут переложены со стержня, на который Брахма сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.

— Легенда профессора Люка

В нашем случае дисков будет не 64, а n; стержней же останется ровно три. Задача та же — перенести набор дисков с одного стержня на другой. Брать за раз можно только один диск; на меньший диск нельзя положить больший.

Дополни определение функции move_stack, которая выводит последовательность шагов для решения задачи о перемещении n дисков со стержня start на стержень end. Приведённая функция print_move должна использоваться для вывода информации о перемещениях дисков.

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

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

    Аргументы:
        n (int): количество дисков
        start (int): начальный стержень, то есть 1, 2 или 3
        end (int): конечный стержень, то есть 1, 2 или 3

    В задаче в точности три стержня, начальный и конечный должны различаться. Предполагается,
    что на начальном стержне находится не менее n дисков увеличивающегося размера, а конечный
    либо пуст, либо верхний диск больше любого другого из 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, "Плохие аргументы"
     "*** ТВОЙ КОД ЗДЕСЬ ***"

Не забудь отправить работу на проверку:

$ git add .
$ git commit -m "Решение всех вопросов"
$ git push