Использование рекурсии для суммирования двух чисел (python)

Question

Мне нужно написать рекурсивную функцию, которая может добавлять два числа (x, y), предполагая, что y не является отрицательным. Мне нужно сделать это, используя две функции, которые возвращают x-1 и x + 1, и я не могу использовать + или - в любом месте кода. Понятия не имею с чего начать, есть подсказки?

Answer 1

Подсказка: вы описываете арифметику Пеано .

Answer 2

Допустим, что

succ(x)=x+1
pre(x)=x-1

Затем (в псевдокоде)

add(x,y) = {
    If(y==0) Return x;
    Return add(succ(x),pre(y))
}

Заметьте, это работает только для неотрицательных значений y.

Answer 3

В комментарии ОП говорится:

я получаю ошибку - "максимальная рекурсия" глубина превышена ".

Вы можете попробовать увеличить предел рекурсии с помощью sys.recursionlimit (после import sys, конечно), но это только поднимет вас до определенного уровня. В Python отсутствует оптимизация, известная как «устранение хвостовой рекурсии», которая (как ни странно, замечательный язык ;-) не делает его лучшим языком для конкретной цели обучения рекурсии (этот лучший язык, IMHO, но не просто на мой взгляд, была бы схема или какой-то вариант Lisp). Таким образом, если y больше максимального предела рекурсии, который вы можете установить на своем компьютере (зависит от системы), эта ошибка неизбежно возникнет.

В качестве альтернативы, вы могли ошибочно закодировать «защиту базовой рекурсии», которая должна возвращаться без дальнейшей рекурсии, когда y равно 0, или вы, возможно, пытались вызвать функцию с y < 0 (что неизбежно "рекурсивно бесконечно", т. е. выдает вышеупомянутую ошибку, когда неизбежно превышен максимальный предел рекурсии).

Answer 4

псевдокод:

for i = 0 to y
    x = f(x)
next

где f (x) - ваша функция, которая возвращает x + 1

или, если вы не можете сделать цикл for, потому что для этого требуется + s:

while (y > 0) {
    x = f(x)
    y = g(y)
}

где f (x) - функция, которая дает x + 1, а g (y) - функция, которая дает y-1

Answer 5

def sum(a,b):
    if b==0:
        return a
    return sum(a+1,b-1)

Answer 6

Звучит как домашняя работа. Так что это, вероятно, обман:

a+b совпадает с a.__add__(b) и

a-b совпадает с a.__sub__(b).

Таким образом, вы можете легко добавлять или вычитать два числа без использования +/-. Нет необходимости в рекурсии.