CODEWITHSUNDEEP
c
osama
osama

Reputation: 11

Recursive function that divides two numbers, using successive subtraction

I have tried but failed to do so. Could I have a push in the right direction?

Upvotes: 0

Views: 10131

Answers (1)

paxdiablo
paxdiablo

Reputation: 882586

I should stress first that this is usually a spectacularly bad usage for recursion. The best recursive solutions tend to reduce the "search space" of the solution rather quickly, such as a binary search removing half the remaining search space with every iteration.

Repeated subtraction will, if the subtrahend is relatively small compared to the minuend (where minuend - subtrahend gives you the difference), result in a great many recursive calls and quite possibly exhaust your stack space.

Having said that, the solution below is in pseudo-code only, since it's probably homework:

def divu (a, b):
    if a < b return 0
    return divu (a - b, b) + 1

It works by repeatedly subtracting b from a, and going down a level, until you can no longer subtract b from a without going negative. Then it returns up the recursion tree, adding 1 for each level you went down.

This will only work for non-negative values of a and positive values of b (hence the divu name for unsigned), though fixing it for negatives and divide-by-zero is only a little extra work.

Some hints for handling signs and errors:

  • Detect straight up if b is equal to zero and exit with an error, exception, or some other mechanism.
  • Treat -a / -b as a / b.
  • Treat -a / b as -(a / b).
  • Treat a / -b as -(a / b).
  • Otherwise, just work out a / b.

It's possible to handle those special cases in a single recursive call but it adds unnecessary checking at each level of recursion. It's probably more efficient to provide a checking function div which can then call divu to do the recursive bit, something like:

def div (a, b):
    if b == 0
        exit with error
    if a < 0 and b < 0:
        return divu (-a, -b)
    if a < 0:
        return -divu (-a, b)
    if b < 0:
        return -divu (a, -b)
    return divu (a, b)

Upvotes: 6

Related Questions