Division using recursion

Question

I am pretty sure that this must be some glaringly stupid mistake by me. But can anyone explain what is wrong in this division code using recursion. I know there are a lot of alternatives, but I need to know what is wrong with this

def division(a, b):
    x = 0
    if a < b:
        return x
    else:
        x += 1
        return division(a - b, b) 
    return x

When I do division(10, 2), it gives me 0 as output

Answer 1

You always set your local variable x to 0.

Then if the dividend is smaller than the divisor you return that x which is of course 0.

On the other hand when the dividend is greater or equal to the divisor you increment x by 1 and do a recursive call with a decremented dividend which will of course lead to the first case at the end and still you return an x which holds the value of 0.

Note: Nonetheless your final return is not reachable since both your if and else branch contains a return.

So please try considering this solution:

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

Update:

A possible solution for working with negative integers following python's round towards negative infinity division:

def division_with_negatives(a, b):
    a_abs, b_abs = abs(a), abs(b)
    if (a >= 0 and b >= 0) or (a < 0 and b < 0):
        # branch for positive results
        if a_abs < b_abs:
            return 0
        else:
            return 1 + division_with_negatives(a_abs - b_abs, b_abs)
    else:
        # branch for negative results
        if b_abs > a_abs or a_abs == b_abs:
            return -1
        else:
            return -1 + division_with_negatives(a_abs - b_abs, -b_abs)


assert division_with_negatives(-4, 1) == -4 // 1
assert division_with_negatives(10, 2) == 10 // 2
assert division_with_negatives(1, -5) == 1 // -5
assert division_with_negatives(-3, -2) == -3 // -2

Answer 2

This might save you from RecursionError:

def div(x, y):
if y == 0: 
    return 0
elif x == y:
    return 1
elif x < y:
    if y * -1 == x:
        return -1
    elif x % y == 0:
        return 1 + div(x - y, y)
    else:
        return 0
else: 
    if y < 0:
        return 1 - div(x - y, -y)
    else:
        return 1 + div(x - y, y)

#Application    
A = div(1, 2)
B = div(-9, 9)
C = div(3, 2)
D = div(-9, -3)
E = div(100, -2)
print(A)  # 0
print(B)  # -1
print(C)  # 1
print(D)  # 3
print(E)  # -50

Answer 3

Your escape condition is if a < b. That means that for this function to terminate, this must be fulfilled to leave the recursion. However, because x is declared at the top of the function, only redefined inside the body of the else statement but never returned, the function will always terminate with a value of x = 0.

You should either set x = 1 + division(a-b,b) or return division(a-b,b) + 1 and remove the unreachable returnat the end.

def div(a, b, x):
    if a < b:
        return x
    else:
        x +=1
        return div(a - b, b, x)

print(div(130, 10, 0))

# 13

Answer 4

This might work a little better for you:

def division(a,b,x=0):
    if a < b:
        return x
    else:
        x += 1
        return division(a-b,b,x) 
    return x

Every time your function ran through a new recusion, you were setting x to 0. This way, it defaults to 0 if x is not specified, and should work like I think you want.

Also note that this will not work for negative numbers, but you probably knew that :)

Answer 5

With global you get:

def division(a,b):
    global x
    if a < b: return x
    else:
        x += 1
        return division(a-b,b) 

x=0  
print (division(10,2))

But you have to set x to zero every time before call the division