improve recursion for calculating remainder

user_11694834 0
Viewed 260

I had to write a code to calculate the remainder using a certain way. I know that there are better ways to do it but that's how I have to proceed.

The if (rem(x - 1, y) + 1 == y) is making extra calls. As it enters there every time before getting to the last return, but it is an important step for my algorithm. I was wondering if there was any way to avoid it.

Also, I know that I have to check if y == 0; I am just trying to improve the performance for now.

Thanks

int rem(int x, int y) 
{
    if (x == 0) 
    {
        return 0;
    }
    if (rem(x - 1, y) + 1 == y) 
    {
        return 0;
    }
    return rem((x - 1), y) + 1;
}

I get 9 recursive calls for rem(3/2)

recursion c algorithm c++ java
2 Answers

Sure, this is how you can make it much better.

int rem(int x, int y) {

    if (x == 0) {
        return 0;
    }

    int ret = rem(x - 1, y);

    if (ret + 1 == y) {
        return 0;
    }

    return ret + 1;
}

We can just call the function once and store its output in a variable.

user_88132670

Yeah sure, In java you do this in following way:

public static void main(String args[]) {
    int remainder = remainder(3,2);
    System.out.println(remainder);
}

static int remainder(int n1, int n2) {
    int x;
    x = n1;
    if (x >= n2) {
        x = x - n2;
        remainder(x, n2);
    }
    return x;
}

Note: I've not added condition to check 0 in the code. Hope this helps.

user_74356990
Related