1

Есть задача:

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

К сожалению, на значениях m, n = -10779,-15755 сталкиваюсь с исключением RecursionError: maximum recursion depth exceeded in comparison. Попытка задать лимит для количества рекурсий не даёт результатов, когда целочисленные значения возрастают до 100 000 - память не позволяет приблизиться к этим числам.

Пока остановились с преподавателем на том, что эту задачу посредством Python 3.9 не решить.

Возможно здесь есть те, кто может доказать обратное. Хочется посмотреть какими средствами можно справиться.

3
  • Пожалуйста, уточните вашу конкретную проблему или приведите более подробную информацию о том, что именно вам нужно. В текущем виде сложно понять, что именно вы спрашиваете. 15 дек 2021 в 14:29
  • Во-первых, есть Stackless Python: ru.stackoverflow.com/questions/1220820/… 15 дек 2021 в 14:51
  • @Stanislav, всё оч просто. Вот текст задачи, который нужно решить конкретно через рекурсию. Не идёт речи о том, что это хорошо/плохо. Речь идёт о том, чтобы исследовать python на возможность решения такой задачи. Я придумать ничего не смог. 16 дек 2021 в 8:11

2 ответа 2

6

Отличная задача. Спасибо!

Чтобы обойти ограничение на глубину рекурсии нужно заменить линейную рекурсию на древовидную. Число операций в линейной рекурсии равно её глубине. Число операций в древовидной рекурсии можно довести до степени двойки от её глубины.

Функция tree_add может сделать до level^2 операций. Если этого хватило чтобы обнулить b (второй элемент p), хорошо. Если нет, функция возвращает неполный результат.

# level - неотрицательное число
# p - пара чисел (a, b), которые нужно сложить
# если |b| <= 2^level, то функция вернёт (a + b, 0)
# иначе функция вернёт (a + 2^level, b - 2^level), если b > 0
# или                  (a - 2^level, b + 2^level), если b < 0
def tree_add(level, p):
    if level == 0:
        a, b = p
        if b == 0:
            return a, 0
        if b > 0:
            return a + 1, b - 1
        if b < 0:
            return a - 1, b + 1
    return tree_add(level - 1, tree_add(level - 1, p))

Функция linear_add вызывает tree_add до тех пор пока та не сумеет выполнить всю работу. Уровень каждый раз увеличивается на единицу, соответственно tree_add может выполнить в два раза больше работы:

def linear_add(level, p):
    a, b = tree_add(level, p)
    if b == 0:
        return a
    return linear_add(level + 1, (a, b))

Верхний уровень - просто сложение:

def add(a, b):
    return linear_add(0, (a, b))

Можно показать что глубина рекурсии не превосходит 2log2(b), что позволяет обрабатывать числа до 2^500.

@>>> add(1_000_000, 1_000_000)
2000000 
5
  • Stanislav Volodarskiy - Вы шикарно обошли ограничения! Единственное не совсем понятное место: а аргументы в tree_add - симметричные? то есть, не имеет смысла заморачиваться, что там уровень, а что - число?
    – S.H.
    15 дек 2021 в 17:14
  • 1
    @S.H., добавил толстый комментарий в заголовок tree_add. 15 дек 2021 в 17:20
  • @S.H., спасибо. Да, решение изящное. Это третий вариант. Первые два были страшненькие. Но, может быть есть что-то ещё более изящное. 15 дек 2021 в 18:18
  • Нет, с таким изяшным решением соревноваться бесполезно! На самом деле, Вы своим ответм ума прибавили не только автору вопроса, но и "болельщикам"!
    – S.H.
    15 дек 2021 в 18:20
  • @StanislavVolodarskiy, это потрясающе! Спасибо, что ещё раз вселили в меня уверенность, что в Python возможно всё.P.S., конечно, это не значит, что его надо сувать во все разные места. 16 дек 2021 в 8:20
0

Можно еще такую матрешку попробовать:

def rec_add(x,y):
    f = lambda a,b,i=1000: (a,b) if not i or b==0 else f(a+1,b-1,i-1) if b>0 else f(a-1,b+1,i-1)
    if y==0: return x
    return rec_add(*f(x,y))

rec_add(1000000,1000000)
'''
2000000
7
  • Упомяните что вам нужен sys.setrecursionlimit(2002) или больше. 15 дек 2021 в 19:57
  • @StanislavVolodarskiy, возможно. У меня питон 3.8, работает на значениях по умолчанию.
    – SergFSM
    15 дек 2021 в 20:22
  • сделал sys.getrecursionlimit() показывает 3000
    – SergFSM
    15 дек 2021 в 20:56
  • У меня Linux 64. Python 3.5, 3.7, 3.9, 3.10. Везде 1000. 15 дек 2021 в 21:06
  • Исходный код 3.8 - значение 1000 в исходном коде. Подозреваю что вы запускаете Питон не напрямую. Юпитер ноутбук? 15 дек 2021 в 21:15

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.