Using recursion to sum two numbers (python)

Question

I need to write a recursive function that can add two numbers (x, y), assuming y is not negative. I need to do it using two functions which return x-1 and x+1, and I can't use + or - anywhere in the code. I have no idea how to start, any hints?

Answer 1

Big hint: you're describing Peano arithmetic.

Answer 2

This sounds like homework. So this is probably cheating:

a+b is the same as a.__add__(b), and

a-b is the same as a.__sub__(b).

So you can easily add or subtract two numbers without using +/-. No need for any recursion.

Answer 3

Lets say that

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

Then, (in pseudocode)

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

Observe, this only works for non-negative y.

Answer 4

pseudo-code :

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

where f(x) is your function that returns x+1

or, if you can't do a for loop because that requires +s :

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

where f(x) is the function that gives x+1 and g(y) is the function that gives y-1

Answer 5

In a comment the OP says:

I get an error - "maximum recursion depth exceeded".

You can try upping the recursion limit with sys.recursionlimit (after an import sys, of course), but that will only get you up to a point. Python does not have the optimization known as "tail recursion elimination", which (wonderful language as it may be;-) does not make it the best language to use for the specific purpose of teaching about recursion (that best language, IMHO but not just in my opinion, would be Scheme or some variant of Lisp). So, when y is larger that the maximum recursion limit you can set on your machine (system dependent), that error will inevitably ensue.

Alternatively, you may have miscoded the "base-recursion guard" which is supposed to return without further recursion when y equals 0, or you may have tried calling the function with a y < 0 (which will inevitably "recurse infinitely", i.e., produce the above mentioned error when the maximum recursion limit is, inevitably, exceeded).