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?
6 Answers
Big hint: you're describing Peano arithmetic.
Comments
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.
2 Comments
James
Okay, I think I get it. I know that (x-1) + (y+1) is going to be the same as x + y. What you did was pretty similar to what I tried, but I get an error - "maximum recursion depth exceeded". I'd post my code but I don't know how to format it properly, is there a link or something? The FAQ didn't have any info on it.
outis
@James: Simply indent each line an additional four spaces. For more formatting information, look for the orange question mark in the post editor toolbar.
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).
Comments
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
2 Comments
tzot
I fixed your misspelled “pseudo”. Note that your answer contains code that's not python, which was on of the tags of the question.
chris
chuckle thanks for that, it was getting late. i'm not a python expert so that's why i wrote pseudo-code (or however you spell it) but i'm sure it won't be hard to convert 3 or 4 lines into proper python...
def sum(a,b):
if b==0:
return a
return sum(a+1,b-1)
Comments
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.
Comments
log(exp(x)*exp(y))is against the rules too, eh?