Find product of two numbers using addition and subtraction only?

user_11614583 0
Viewed 1803

This is my problem statement. Given two integers m & n, calculate and return their multiplication using recursion. You can only use subtraction and addition for your calculation. No other operators are allowed.

This is my approach.

def mult(m,n):
    if m == 0 or n == 0:
        return 0
    if n == 1:
        return m
    if m == 1:
        return n
    if m < 0 and n < 0:
        return mult(-m, -n)
    if n < 0:
        return -mult(m, -n)
    if m < 0:
        return -mult(-m, n)
    return m + mult(m, n - 1) 

m = int(input())
n = int(input())
print (mult(m, n))

One of the test case is showing Runtime Error. Could someone please tell me what is problem with my code. I have also taken care of negative values.

Runtime Error
Traceback (most recent call last): File Main.py , line 18, in <module> print (mult(m, n)) 
File Main.py , line 14, in mult return m + mult(m, n - 1) 
File Main.py , line 14, in mult return m + mult(m, n - 1) 
File Main.py , line 14, in mult return m + mult(m, n - 1) 
File Main.py , line 14, in mult return m + mult(m, n - 1) 
File Main.py , line 14, in mult return m + mult(m, n - 1) 
File Main.py , line 14, in mult return m + mult(m, n - 1)
recursion python-3.x python
5 Answers

I tested your script for several inputs and found out that it does not work for higher numbers. For example, it is not working for m,n (3412 * 3412). The reason for this is that the recursion depth in python which is 1000 by default is being crossed in your code.

To increase the recursion depth in python follow the steps:

1) import the sys module in your script and

2) At the beginning of your script Type this :

 sys.setrecursionlimit(1500)

This will increase the default limit(1000) to 1500.

Note: Though it works for your code up to some number, it is not a good solution. You need to improve your code.

Hope this will help you.

user_102688160

Since your code works fine for other cases, I feel the error might be because of max recursion depth. You can do something like below, with out using recursion. Below code uses loops and addition, for and sum.

def mult(m, n):
    result = sum(m for _ in range(abs(n)))
    if n < 0:
        return -result
    else:
        return result


m = int(input())
n = int(input())
print(mult(m, n))

Output:

3
-12
-36
user_114508730

Try one number greater than 1000 and check

python recursion limit is 1000 only you can change it by using 'sys' module

sys.setrecursionlimit(1500)

this might help.

user_73647360

Thank you everyone for helping me out to find error. Actually it was recursion limit which was giving problem when I changed it to higher value as suggested by 'tobias_k' using

import sys
sys.setrecursionlimit(1000)

this solved my problem.

user_116145830 
def mul(m, n):
     return m if n == 1 else m + (m, n - 1)
user_169165610
Related