CODEWITHSUNDEEP
javaalgorithm
Ordo
Ordo

Reputation: 705

Summing integers recursive with Java

I have to calculate a sum of two integers by using a recursive algorithm, but sincerely i have no idea how to do so. Here are the conditions:

sum(x,y) = ?
if x = 0 then sum (x,y) = y otherwise sum(x,y) = sum(predecessor(x),successor(y)).

Does someone have an idea how i could write this in an algorithm? I would be glad about any advice.

Upvotes: 0

Views: 1664

Answers (5)

aioobe
aioobe

Reputation: 420951

Javaish pseudo code corresponding to your code in your question

sum(x, y): return x == 0 ? y : sum(x-1, y+1)

Works for any pair of numbers where x is a non-negative integer.

Upvotes: 1

Peter Lawrey
Peter Lawrey

Reputation: 533492

To handle negative numbers based on @aioobe's answer.

sum(x, y): return x == 0 ? y : x < 0 ? ~sum(~x, -y) : sum(x-1, y+1)

Note: the rather optimisic use of ~ to avoid blowing up on x=MIN_VALUE. ;)

Upvotes: 1

user467871
user467871

Reputation:

Here is my solution for i&j both >= 0. set sum = 0; and subtract 1 until it is <= 0 

 public static int sum(int i, int j){
           return sum(i,j,0);
 }

 private static int sum(int i, int j, int sum) {
    if (i <= 0 && j <= 0) {
        return sum;
    } else if (i <= 0) {
        return sum(0, j - 1, sum + 1);
    } else if (j <= 0) {
        return sum(i - 1, 0, sum + 1);
    } else {
        return sum(i - 1, j - 1, sum + 2);
    }
}

    public static void main(String[] args) {
        System.out.println(sum(60, 7)); 

    }

Upvotes: 1

Hons
Hons

Reputation: 4046

That's the simplest I could immagine

public static void main(String[] args) {
    System.out.println("4+5 = " + sum(4, 5));
    System.out.println("4+(-5) = " + sum(4, -5));
    System.out.println("-4+5 = " + sum(-4, 5));
    System.out.println("-4+5 = " + sum(-4, -5));
}

public static int sum(int x, int y) {
    if (x < 0) {
        x *= -1;
        y *= -1;
    }
    return (x == 0 ? y : sum(--x, ++y));
}

Upvotes: 1

Abhinav Sarkar
Abhinav Sarkar

Reputation: 23782

I won't give you the code since this seems to be a homework but here is the rough algorithm:

predecessor(x) = x - 1
successor(x) = x + 1

sum(x, y) = 
  if x = 0 
    then y 
    otherwise sum(predecessor(x), successor(y))

Upvotes: 7

Related Questions