A. Рекурсивный сумматор

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

Ваше решение будет использоваться как библиотека.

Напишите функцию recursive_sum, которая находит сумму всех позиционных аргументов.

Примечание

Ваше решение должно содержать только функции.
В решении не должно быть вызовов требуемых функций, за исключением рекурсивных.
Трассировка вызова рекурсивной функции в обработке ответа не учитывается и показана для примера.

Пример

Ввод

result = recursive_sum(1, 2, 3)

Вывод

# Вызов recursive_sum(1, 2, 3)
# Вызов recursive_sum(1, 2)
# Вызов recursive_sum(1)
# Вызов recursive_sum()
result = 6

Ввод

result = recursive_sum(7, 1, 3, 2, 10)

Вывод

# Вызов recursive_sum(7, 1, 3, 2, 10)
# Вызов recursive_sum(7, 1, 3, 2)
# Вызов recursive_sum(7, 1, 3)
# Вызов recursive_sum(7, 1)
# Вызов recursive_sum(7)
# Вызов recursive_sum()
result = 23

Решение

Мы затрагиваем тему рекурсий. Одну из самых элегантных и красивых и вто же самое время одну из самых сложных для понимания тем. Для нее даже существует специальная шутка, которая гласит что, “чтобы понять рекурсию, нужно сначала понять рекурсию”. Забавно, что это и есть пример рекурсии. Правда рекурсии неправильной, не имеющей граничного условия и потому бесконечной.

Итак, чтобы понять рекурсию, давайте есть слона по частям.

Давайте предположим что нам надо взвесить груду разномастных кирпичей, но у нас есть весы, которые могут показать вес только одного кирпича. Нам задают вопрос – сколько весит груда этих самых кирпичей?

С точки зрения наивного программирования, мы начнем перебирать все кирпичи и складывать их массу в специальную переменную. Таким образом взвесив последний кирпич мы получим массу всей кучи.

Рекурсивный подход к решению этой задачи ничем не отличается от вышеизложенного за исключением одного нюанса – того, как мы думаем об этой куче.

Если сформулировать решение этой задачи в рекурсивной парадигме, то масса кирпичей равна массе одного взятого из кучи кирпича плюс масса оставшихся кирпичей. И так до тех пор, пока в куче все еще есть кирпичи.

Условие “пока в куче есть кирпичи” называется граничным условием. Оно нужно для того, чтобы рекурсия не превращалась в бесконечный вызов самой себя. Грубо говоря, рекурсивной можно назвать такую функцию, которая отвечает на какой-то маленький частный вопрос (сколько весит этот кирпич), а ответ на остальные вопросы (сколько весит остальная куча) доверяет сама себе, вызывая себя с меньшим количество данных.

Реальный же подсчет массы откладывается до момента, пока мы не найдем ответ на вопрос массы “остальной кучи”. Но рано или поздно мы взвесим последний кирпич и начнем выходить из рекурсии, складывая все запомненные массы кирпичей один за одним ровно так же как бы мы делали это в цикле.

Давайте попробуем написать такую функцию.

Для начала нам нужно принять в качестве параметров неизвестное количество чисел (кирпичей). Это можно сделать с помощью материала прошлой темы, например задачи C. Функциональный НОД 2.0.

Теперь, когда мы разобрались с входными данными давайте вспомним как распаковать список, полученный на вход. Для наших целей достаточно взять его первый элемент, а остаток списка отправить на вход нашей же функции.

В качестве ответа (сколько весит кирпич), наша функция будет возвращать вес этого конкретного кирпича. Теперь нам остается в промежутке между изъятием кирпича и возвращением его веса вызвать нашу функцию с остатком списка.

Ниже представлены два варианта решения задачи. Принципиально они похожи, и отличие только в граничном условии. В первом случае, вызов осуществляется даже в том, случае, когда куча уже оказывается пуста. Во втором – только до тех пор, пока мы не забрали последний кирпич.

def recursive_sum(*nums):
    if not nums:
        return 0
    return nums[0] + recursive_sum(*nums[1:])   

def recursive_sum(*nums):
    while nums[1:]:
        return nums[0] + recursive_sum(*nums[1:])
    return nums[0]