Division by subtracting recursively

[Dartht33bagger]

I just started doing recursion in my C++ class today and I'm starting to get the hang of it. I've already written a function that multiplies two numbers by recursively adding. However, I am getting suck on how to do division of two numbers with recursive subtraction. This is my code so far:

int divide(int a, int b)
{
    if( b == 0 )
    {
        return 0;
    }
    else if( a < b)
    {
        return 0;
    }
    else
    {
        return( a - divide( a + 1, b));
    }
}

I know the else isn't correct though. I'm not exactly sure how to do a - b at each recursion. I'm sure there is an easy solution to this, but I just can't wrap my head around it...

[Vlykarye]

Is it a/b or b/a?

[CJC0117]

Just break it down into small parts.

As you have it now, this is what happens if say, b=6 and a=2:

divide(6,2)=6-divide(7,2)=6-7+divide(8,2)=-1+8-divide(9,2)...

The loop will never end since a is getting larger.

Let's think about division between two numbers. If two numbers divide evenly, then the number of times that the smaller number can be subtracted from the larger number is the quotient. Think about 6/2=3. 6-2=4. 4-2=2. 2-2=0. In total, we subtracted 2 three times.

So what you have to do is count the number of times you subtract b from a before reaching a<b.

Keeping that in mind, re-think your return statement on line 13.

[Dartht33bagger]

It is a / b.

I'm just having a hard time visualizing what a is equal to when I do the return statement. I tried a bunch of different ways of doing it, and the one that make most sense to me was this:

int divide(int a, int b)
{
    if( b == 0 )
    {
        return 0;
    }
    else if( a < b)
    {
       return 0;
    }
    else
    {
        return ( (a - b) - divide( a - b, b) );
    }
}

However, it doesn't supply the right outputs. I guess I'm just having a really hard time wrapping my head around how I can count the number of times I've subtracted b with recursion. I'm also confused as to what a is equal to at certain points. In my return statement above, does the program do (a - b) first and then send ( ( a - b) - b) to divide? Or does it do something completely different? Because if I don't do (a - b) and just put a into the first parameter of divide my program crashes.

[Vlykarye]

Ok.

a = 10
b = 5

a - b = 10 - 5
a - b = 5 - 5
a = 0, must be divisible

try something like this:

int divide(int a, int b)
{
    if( b == 0 )
    {
        return 0;
    }
    else if(a-b == 0)
    {
       return 1;
    }
    else if( a < b)
    {
       return 0; // You will need to think of something better than this.
    }
    else
    {
        return ( 1 + divide(a-b, b) );
    }
}

This will return how many times b goes into a.

[Dartht33bagger]

Oh wow, that is really simple....I guess I just wasn't thinking of it like that. I at least had the parameters in the divide function right. The 1 + divide does make sense now though. Thank you!

[Vlykarye]

No problem. This is a good way to understand recursive functions. Of course, I wouldn't suggest using them this was. As you can see, we don't have a way to return 0 at the very end of the function call when b is not able to divide into a evenly.