Отличная задача. Спасибо!
Чтобы обойти ограничение на глубину рекурсии нужно заменить линейную рекурсию на древовидную. Число операций в линейной рекурсии равно её глубине. Число операций в древовидной рекурсии можно довести до степени двойки от её глубины.
Функция 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