RecursionError: maximum recursion depth exceeded in comparison

Question

Есть задача:

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

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

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

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

Answer 1

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

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

Функция 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

Answer 2

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

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

Answer 3

еще одно из решений - увеличить лимит рекурсий)

sys.setrecursionlimit(10000)

БЛОГ НА HUSL

RecursionError: maximum recursion depth exceeded in comparison

Ответы (3 шт):